16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
1. 풀이방법
- BFS 문제. DFS로도 풀어보았지만 로직은 맞는 것 같지만 역시나 시간 초과가 나옵니다. (코드는 첨부)
- 상어의 위치로 부터 조건에 가장 부합하는 물고기 위치를 BFS로 탐색해 찾아낸 다음
- 그 위치의 물고기를 먹고 상어의크기를 조정이 필요할 경우 해주고 그 위치로 아기상어를 옮겨 주시면 됩니다.
- 저는 DFS를 먼저 풀고 거기서 재활용할 함수들은 재활용하고 makefishcase만 bfs로 바꿔서 구현하여서,
- 불필요한 부분도 들어있습니다. 깔끔하지 않습니다.
2. 주의사항
- 한가지 있는데, 저와 같은 케이스인 분들을 위해 기록합니다.
- bfs로 짰는데 "시간초과" 라는 결과를 얻었습니다.
- 코드를 아무리 봐도 시간초과가 나올만한 연산을 하는 곳이 없습니다.
- 이럴경우 거의 십중팔구 무한루프에 빠지는 테스트케이스가 존재한다는 뜻입니다.
- 그것을 곰곰히 생각해보니,
- 이러한 경우 입니다
9 0 0
4 4 4
0 0 1
-저의 코드에서는 전체 바다에서 먹을 수 있는 물고기가 존재하는지 체크하는 함수가 있는데,
- 그 함수는 이러한 케이스에서 1이라는 물고기가 있으므로 break;를 걸지 않아서 무한루프에 빠져
- 시간초과가 나오는 것이였습니다.
- 물론 종료조건 함수를 훨씬 정교하고 예쁘게 만드셨다면 해당되지 않으실 수 도 있습니다!
3. 나의코드
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int dx[4] = { 1,-1,0,0 }; //상하좌우 4방향 탐색
int dy[4] = { 0,0,-1,1 };
int sea[21][21];
bool visit[21][21];
int N;
int resultsecond;
int tmpeat = 0;
int sharksize = 2;
int sharkx, sharky;
int failsecond = -1;
struct fish {
int x, y, far;
};
vector<fish> farr;
void inputs() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> sea[i][j];
if (sea[i][j] == 9) { sharkx = i; sharky = j; }
}
}
}
bool checksea() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (sea[i][j] > 0 && sea[i][j] < sharksize && sea[i][j] != 9) { return false; }
}
}
return true; //더이상 잡아 먹을 것 이 없음
}
void visitclear() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
visit[i][j] = false;
}
}
}
queue<fish> tmpq;
void makefishcase(int x, int y) {
tmpq.push({ x,y,0 });
int cnt = 0;
while (1) {
int si = tmpq.size();
if (si == 0) { failsecond = resultsecond; break; }
while (si--) {
int tx = tmpq.front().x;
int ty = tmpq.front().y;
tmpq.pop();
if (sea[tx][ty] > 0 && sea[tx][ty] < sharksize && sea[tx][ty] != 9) {
farr.push_back({ tx,ty,cnt });
}
for (int i = 0; i < 4; i++) {
int nextx = tx + dx[i]; int nexty = ty + dy[i];
if (nextx >= 0 && nextx < N && nexty >= 0 && nexty < N) {
if (visit[nextx][nexty] == false && sea[nextx][nexty] <= sharksize) {
visit[nextx][nexty] = true;
tmpq.push({ nextx,nexty,0 });
}
}
}
}
if (farr.empty() == false) break;
cnt++;
}
}
bool compare(fish& lh, fish& rh) {
if (lh.far < rh.far) return true;
else if (lh.far == rh.far) {
if (lh.x < rh.x) return true;
else if (lh.x == rh.x) {
if (lh.y < rh.y) return true;
else return false;
}
else return false;
}
else return false;
}
void queuereset() {
while (!tmpq.empty()) {
tmpq.pop();
}
}
void eatfish() {
queuereset();
makefishcase(sharkx, sharky);
if (failsecond != -1) return;
sort(farr.begin(), farr.end(), compare); //거리 순 > 위에있는순> 왼쪽에 있는순으로 소팅
sea[sharkx][sharky] = 0;
sharkx = farr[0].x; sharky = farr[0].y;
tmpeat++;
if (sharksize == tmpeat) {
tmpeat = 0; sharksize++;
}
sea[sharkx][sharky] = 9;
resultsecond += farr[0].far;
visitclear();
farr.clear();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inputs();
while (1) {
if (checksea()) break;
visit[sharkx][sharky] = true;
eatfish();
if (failsecond != -1) break;
}
if (failsecond == -1) {
cout << resultsecond << "\n";
}
else { cout << failsecond << "\n"; }
return 0;
}'알고리즘 문제풀이 > DFS와 BFS' 카테고리의 다른 글
| 백준 19238 [C++] (0) | 2021.01.17 |
|---|---|
| 백준 17142 [C++] (0) | 2021.01.17 |
| 백준 2644 [C++] (0) | 2020.12.22 |
| 백준 7569 [C++] (1) | 2020.12.20 |
| 백준 1697 [C++] (0) | 2020.12.20 |