[BFS 반복] 백준 16263번 아기 상어 C++

※ 문제

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

※ 풀이

1) 거리가 가장 가까운 물고기들을 찿아야므로 BFS를 이용합니다.

 

* BFS는 가중치가 없는 그래프에서 최단 경로를 구할 때 유용합니다.

 

2) 먹을 수 있는 물고기들을 확인하면서 거리가 가장 가까운 물고기를 저장합니다.

3) 단, 먹을 수 있는 가장 가까운 물고기를 찾을 때마다 아기 상어의 위치와 공간 상태를 업데이트 해야 합니다. 아래 코드의 update() 함수를 이용합니다.

4) 2), 3)을 위해 BFS를 여러 번 반복하여 실행해야 합니다. 

5) 따라서 BFS로 먹을 수 있는 물고기들을 찾다가,

   먹을 수 있는 물고기를 발견할 때마다 거리를 확인하여 거리가 가장 가까운 물고기를 저장하고,

   BFS가 끝나면 update 함수로 앞에서 찾은 물고기 위치로 상어를 이동시킵니다.

   이를 더이상 먹을 수 있는 물고기를 찾지 못할 때까지 반복합니다.

6) 반복이 끝나면 현재 상어 상태에 저장된 상어가 돌아다녔던 시간(time)을 반환합니다.

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

struct pos {
	int x, y, size, time, fish; // 위치, 크기, 시간(거리), 먹은 물고기 수
};

int board[22][22];
int visited[22][22];
int n;
int ans;
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };
pos shark, close; // 상어와 가장 가까운 물고기 상태 저장
queue<pos> q;

// 먹을 수 있는 물고기들 중 가까운 물고기 저장
void findClosest(pos check) {
	if (close.x == 0) close = check;
	else {
		if (check.time < close.time) { // 가까운 물고기 선택
			close = check;
		}
		else if (check.time == close.time) {
			if (check.y < close.y) close = check; // 위쪽 물고기 선택
			else if (check.y == close.y) {
				if (check.x < close.x) close = check; // 왼쪽 물고기 선택
			}
		}
	}
}

// 거리 가까운 물고기 위치 찾기
void bfs() {
	memset(visited, 0, sizeof(visited)); // visited 초기화 조심
	close = { 0,0,0,0,0 };
	visited[shark.y][shark.x] = 1;
	q.push(shark);

	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		int size = q.front().size;
		int time = q.front().time;
		int fish = q.front().fish;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			
			if ((newX == 0) || (newY == 0) || (newX == n + 1) || (newY == n + 1)) continue;
			if (visited[newY][newX]) continue;
			if ((board[newY][newX] == 0 ) || (board[newY][newX] == size)) {
				visited[newY][newX] = 1;
				q.push({ newX, newY, size, time + 1, fish });
			}
			else if (board[newY][newX] < size) {
            	// 가장 가까운 물고기 선택
				findClosest({ newX, newY, size, time + 1, fish + 1 });
			}
		}
	}
}

// 물고기 먹기, board, shark 위치 업데이트
void update() {
	board[shark.y][shark.x] = 0;
	board[close.y][close.x] = 9;

	if (close.fish == close.size) { // 물고기 사이즈 증가
		close.size++;
		close.fish = 0;
	}
	shark = close; // 상어 이동
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int temp = 0;
	cin >> n;

	memset(board, 0, sizeof(board));
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> temp;
			if (temp == 9) {
				shark = { j, i, 2, 0, 0 };
			}
			board[i][j] = temp;
		}
	}

	while (true) {
		bfs(); // 가장 가까운 물고기 찾기

		if (close.x == 0) { // 먹을 수 있는 물고기 없음
			ans = shark.time;
			break;
		}
		
		update(); // 물고기 먹기, 보드 상태 업데이트
	}
	
	cout << ans;

	return 0;
}

 

※ 수정 전 코드

BFS를 1번만 사용하면 되는 줄 알았는데 아래 방식으로 풀면 상어의 위치와 공간 업데이트를 할 수 없습니다.

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

struct pos {
	int x, y, size, time, fish;
};

int board[22][22];
int visited[22][22];
int n;
int ans;
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };
queue<pos> q;

void bfs() {
	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		int size = q.front().size;
		int time = q.front().time;
		int fish = q.front().fish;
		q.pop();
		
		if (ans < time) ans = max(ans, time);
		
		for (int i = 0; i < 4; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			
			if ((newX == 0) || (newY == 0) || (newX == n + 1) || (newY == n + 1)) continue;
			if (visited[newY][newX]) continue;
			if ((board[newY][newX] == 0 ) || (board[newY][newX] == size)) {
				visited[newY][newX] = 1;
				q.push({ newX, newY, size, time + 1, fish });
			}
			else if (board[newY][newX] < size) {
				board[newY][newX] = 0;
				visited[newY][newX] = 1;
				if (fish + 1 == size) {
					q.push({ newX, newY, size + 1, time + 1, 0 });
				}
				else {
					q.push({ newX, newY, size, time + 1, fish + 1 });
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int temp = 0;
	cin >> n;

	memset(board, 0, sizeof(board));
	memset(visited, 0, sizeof(visited));

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> temp;
			if (temp == 9) {
				visited[j][i] = 1;
				q.push({ j, i, 2, 0, 0 });
				continue;
			}
			board[i][j] = temp;
		}
	}

	bfs();

	cout << ans;

	return 0;
}