[BaekJoon] 16236 - 아기 상어
알고리즘 문제 풀이
문제
안녕하세요.
백준에서 삼성 SW 역량 테스트 기출 문제집에 게시된 16236번 아기 상어 문제 풀이를 소개하겠습니다.
이 문제는 아기 상어가 N x N 크기의 공간에서 자신보다 작은 물고기를 잡아 먹으면서 성장을 하는 문제 입니다.
상어가 최단거리의 물고기의 위치를 탐색하는 것이 이 문제의 포인트 입니다. 물고기 위치를 탐색하기 위해 DFS가 아닌 BFS를 활용해야 합니다. DFS보다 BFS의 난이도가 좀 더 높은 편입니다. 그 이유는 한 방향의 길을 계속 이어서 탐색하는 것이 아니고, 매번 다른 방향에서의 이동 거리와 조건을 체크해줘야 하기 때문입니다. 자세한 내용은 아래에서 확인하도록 하겠습니다.
주어진 정보
- 상어의 처음 크기는 2
- 자신의 크기 만큼의 물고기를 먹으면 상어의 크기는 +1
- 물고기의 크기는 최대 6
- 한 칸을 이동할 때 마다 1초가 지나고, 물고기를 잡아 먹는 시간은 0초
- 상어는 자신보다 작은 물고기만 먹을 수 있고, 같은 크기의 물고기는 지나가는 것만 가능
- 더 이상 먹을 수 있는 물고기가 없으면 종료
해결 방향
먼저 문제에서 요구하는 출력은 상어의 이동 시간(이동 거리)이기 때문에, BFS를 진행 할 때 마다 이동 거리를 return 하도록 합니다. 이렇게 물고기를 먹을 때 마다 BFS 를 진행하고, 물고기를 더 이상 먹을 수 없다면 지금 까지 이동한 시간을 출력하면 됩니다.
BFS의 순서는 다음과 같습니다.
- 먹을 수 있는 물고기가 없으면 종료. (남은 물고기의 수가 0)
- 현재 상어 위치를 비어있는 큐에 넣음
- BFS 탐색
- 큐가 비어 있으면 탐색 종료
- 큐에서 맨 앞을 꺼내서 먹을 수 있는 물고기면
- 최단 거리 체크
- 위치 우선 순위 체크 (제일 위, 제일 왼쪽 우선 순위)
- 먹은 물고기 위치 갱신 후, 다시 큐에서 꺼내는 단계로 이동
- 현재 위치에서 +1 칸 이동 시도 ( 동,서,남,북 네 방향 )
- 영역 바깥, 중복 방문, 물고기 크기 체크
- 이동 가능한 칸을 큐의 맨 뒤에 삽입
- 최단 거리의 물고기를 먹고 상어의 위치 갱신
전체 코드와 주석이 위의 내용처럼 아래에 작성되어 있습니다.
풀이
풀이 코드
#include <iostream>
#include <vector>
using namespace std;
int N; // 공간 크기
int sz_shark, cnt_fish, cnt_eat; // 상어 크기, 총 물고기 수, 먹은 수
int dd[][4] = { {-1,0,1,0,},{0,1,0,-1} }; // 방향 우선순위 불가능
vector< vector <int> > arr; // 공간
pair<int, int> pos_shark; // 상어가 있는 좌표
// 상어가 이동 가능한 영역인지 체크
bool check_way(int r, int c) {
if (r < 0 || r >= N) return false;
if (c < 0 || c >= N) return false;
return true;
}
// 상어가 물고기를 먹고 위치, 크기 갱신
void eat_fish(pair<int, int> fish) {
arr[fish.first][fish.second] = 9;
arr[pos_shark.first][pos_shark.second] = 0;
pos_shark = fish;
cnt_fish--;
cnt_eat++;
if (cnt_eat == sz_shark) {
cnt_eat = 0;
sz_shark++;
}
}
// BFS를 이용해 다음에 먹을 물고기를 찾아 이동 거리를 리턴
int find_target() {
vector< vector<int> > arr_visited = vector< vector<int> >(N, vector<int>(N, -1)); // BFS 탐색을 위한 방문 지도, 각 칸에는 해당 좌표까지의 이동 거리 값 계산
vector< pair<int, int> > Q; // BFS 탐색을 위한 큐
Q.push_back(pos_shark); // 큐에 처음 시작 위치를 상어 위치로 넣음
arr_visited[pos_shark.first][pos_shark.second] = 0; // 처음 시작 위치는 이동거리 0
int dist_min = N * N;
int r_min, c_min;
r_min = c_min = N;
// 탐색 초기화 끝
while (true) {
// 큐가 비어 있으면 종료
if (Q.size() == 0) break;
// 맨 앞에서 다음 탐색 위치 꺼냄
pair<int, int> pos = Q.front();
Q.erase(Q.begin());
// 다음 이동하는 위치가 상어보다 작은 물고기가 있는 위치인 경우, (물고기의 크기는 6보다 크지 않음)
if (arr[pos.first][pos.second] < sz_shark &&
arr[pos.first][pos.second] != 0 && arr[pos.first][pos.second] != 9 &&
arr_visited[pos.first][pos.second] <= dist_min) {
// 더 짧은 거리의 먹을 수 있는 물고기가 있다면, 최소 이동 거리 갱신, 아마 BFS 특성상 자동으로 만족?
if (arr_visited[pos.first][pos.second] < dist_min)
dist_min = arr_visited[pos.first][pos.second];
// 우선순위에 따른 물고기 위치 선택
if (pos.first <= r_min) {
r_min = pos.first;
if (pos.second < c_min) {
c_min = pos.second;
}
}
continue;
}
// 현재 위치에서 네 방향으로 이동 가능한 위치 탐색
for (int way = 0; way < 4; way++) {
int r_ = pos.first + dd[0][way];
int c_ = pos.second+ dd[1][way];
int dist_next = arr_visited[pos.first][pos.second] + 1; // 다음 이동 거리는 현재에서 +1 만큼
if (check_way(r_, c_) == false) continue; // 공간 바깥 체크
if (arr_visited[r_][c_] != -1 && arr_visited[r_][c_] <= dist_next) continue; // 중복 방문 체크
if (arr[r_][c_] > sz_shark) continue; // 상어보다 큰 물고기 체크
// 이동 조건에 만족하면 큐에 삽입
Q.push_back(pair<int, int>(r_, c_));
arr_visited[r_][c_] = dist_next;
}
}
// 한번도 이동을 못했다면 이동거리는 0
if (dist_min == N * N)
return 0;
else
eat_fish(pair<int, int>(r_min, c_min));
return dist_min;
}
int solution() {
int t = 0;
// 물고기를 먹을 수 없을 때 까지 반복
while (cnt_fish > 0) {
int dist = find_target(); // BFS를 이용해 먹이를 찾고 이동 거리를 리턴
if (dist == 0) break; // 이동 하지 못하면 종료
t += dist; // 이동 거리만큼 시간을 늘림
}
return t;
}
int main() {
cin >> N;
arr = vector< vector <int> >(N, vector<int> (N, 0));
cnt_eat = cnt_fish = 0;
sz_shark = 2;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
cin >> arr[r][c];
if (arr[r][c] > 0 && arr[r][c] < 9) cnt_fish++;
if (arr[r][c] == 9) pos_shark = pair<int, int>(r, c);
}
}
cout << solution() << endl;
return 0;
}
다른 테스트 케이스
혹시 예제 케이스는 통과 했는데, 답안 코드 제출시 틀린다면 아래의 케이스들을 테스트 해보길 바랍니다.
10
0 1 4 6 1 4 5 4 0 3
2 0 0 9 0 0 6 0 0 0
4 3 2 4 6 3 0 2 1 6
0 0 0 0 1 0 0 1 0 6
0 0 0 6 0 4 1 4 0 1
0 3 0 1 6 0 3 1 0 4
6 5 0 2 0 0 5 1 0 1
0 4 0 4 1 1 2 5 6 6
1 0 5 6 5 1 0 1 2 0
5 6 3 0 6 0 1 1 6 0
answer:103
10
5 6 3 0 5 5 4 4 3 0
2 4 0 4 0 1 0 1 0 6
0 3 4 1 0 0 3 1 1 0
0 5 1 0 1 6 1 3 5 1
0 3 0 1 1 0 4 0 1 0
0 5 1 5 6 0 3 4 0 9
0 5 5 3 0 0 4 5 0 3
2 5 0 3 3 2 0 0 3 2
2 6 5 0 0 4 1 1 6 3
1 3 1 3 0 1 0 0 0 5
answer:105
10
5 3 2 0 0 1 2 0 4 0
3 0 3 1 0 0 3 0 6 1
0 3 0 5 0 5 4 4 2 5
3 0 0 3 0 6 1 5 4 2
1 0 2 0 2 0 3 0 0 6
1 1 1 1 1 1 1 1 0 0
2 0 2 1 9 6 0 0 4 3
1 6 1 0 6 0 5 0 1 0
6 5 4 0 1 2 1 3 5 0
0 1 6 6 1 4 3 0 1 1
answer:102
10
2 0 2 0 1 1 1 0 1 0
0 4 4 0 4 0 0 0 3 0
4 3 5 0 1 0 2 6 0 0
0 0 5 5 3 1 3 1 3 4
6 0 5 1 4 2 4 0 5 0
0 0 5 0 2 1 1 2 1 0
2 0 5 2 4 0 9 1 6 2
4 1 2 0 3 0 3 2 4 6
3 0 1 0 4 0 0 5 0 1
0 4 1 1 6 6 1 6 0 0
answer:87
해설
- solution() : 먹을 수 있는 물고기 수 만큼 while loop를 수행
- find_target() : BFS 를 수행하는 함수, 이동 거리를 리턴
- eat_fish() : 먹을 수 있는 물고기가 있을 때, 상어의 위치를 바꾸고 먹은 횟수와 남은 물고기 수를 갱신
앗 이걸 생각 못했네?
- 문제에는 명시되어 있지 않지만, 상어 크기 성장 시 먹은 횟수는 0으로 초기화 해야 합니다.
- 물고기는 최대 크기가 6이기 때문에 상어는 7까지만 커져도 됩니다.
- 상어가 8 이상으로 커지는 경우, 초기 큐에서 상어의 위치를 꺼내다가 빈곳이 아니므로 물고기를 먹은것으로 잘못 처리 할 수 있습니다.
- 제 풀이에는 상어의 크기에 대한 제한이 없기 때문에 물고기를 먹는 조건에 9는 못먹게 해놓았습니다.
- 체크해야할 조건들이 많기 때문에 조건 처리 실수를 조심해야 합니다.
- 중복 방문 체크시, 현재 이동 거리와 같거나 작으면 가지 않는다. 이동 거리가 같은데 다시 큐에 넣는 것은 계산 및 시간 낭비를 유발 합니다.
- 방향 우선 순위 비교를 위한 비교연산자 체크 (이상/초과, 이하/미만)