[PS] 백준 16236 : 아기상어

문제

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

16236번: 아기 상어

 

해설

 

일반적인 BFS 완전탐색을 이용한 시뮬레이션 문제 입니다. 이 문제를 해결하는 핵심 키워드는 바로 문제의 조건에 있습니다. 문제에서는 다음과 같은 조건을 포함하고 있습니다. 

 

1. 먹을 수 있는 물고기가 1마리 이상이라면 

 

2. 가장 가까운 물고기를 먹는다.

 

2-1. 가장 가까운 물고기가 여러마리 일 경우 가장 위쪽 물고기를 먹는다. 

 

2-2. 그러한 물고기가 여러마리라면 가장 왼쪽 물고기를 먹는다. 

 

이 때 흔히하는 실수가 탐색방향을 단순히 상, 좌 .. 이런식으로 하면 되지 않냐는 착각에 빠지게 되는데 이를 자각하지 못하면 왜맞틀의 늪에 빠지게 됩니다. 

 

PS 문제들 중 특히 시뮬레이션이나 완전탐색 문제의 경우 자신이 생각하는 최적의 방향이 또는 최적의 결과 값이 최소 또는 최대 값이라고 생각하는 착각에 빠지게 되는데, 다차원 함수에서 어떤 극소점이 Local Minimum 일 수는 있지만 Global Minimum임을 보장할 수 없는 것과 같은 맥락입니다. 

 

때문에 먹을 수 있는 물고기들 중에서 어떠한 물고기를 먹을지 선택하는 과정을 구현해야합니다.

 

코드

/**
 * 알고리즘 : BFS
 * 1. 이 문제의 포인트는 local minimum이 global minimum 이라는 착각에 빠지지 않는 것이다.
 * 2. 문제의 조건 중 거리가 가까운 물고기가 여러마리가 있으면 
 * 3. 우선순위가 상, 좌 이므로 이를 고려하여 이동해야 하는데 
 * 4. 방향이동을 단순히 상 좌 하 우 이런식으로 한다고 해서 우선순위에 맞게 탐색이 진행될거란 보장이 없다.
 * 5. 때문에 이를 처리해주는 코드가 필요하다.
 */

public class BOJ_16236_아기상어 {
	StringBuilder sb = new StringBuilder();
	static int n;
	static int[][] map;
	static int sx, sy;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int s, c;
	static int total;
	static boolean bfs() {
		Queue<int[]> q = new LinkedList<>();
		boolean[][] visit = new boolean[n][n];
		int time = 0;
		q.add(new int[] { sx, sy });
		visit[sx][sy] = true;
		
		int tx = n, ty = n;
		
		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				int[] pos = q.poll();

				for (int dir = 0; dir < 4; dir++) {
					int nx = pos[0] + dx[dir];
					int ny = pos[1] + dy[dir];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n || visit[nx][ny] || map[nx][ny] > s)
						continue;
					// 먹을 수 있는 물고기인 경우 물고기의 좌표를 우선순위에 따라 갱신한다.
					if(map[nx][ny] > 0 && map[nx][ny] < s) {
						if(nx <= tx) {
							if(nx == tx) {
								ty = Math.min(ty, ny);
							} else {
								tx = nx; ty = ny;
							}
						}
					}
					visit[nx][ny] = true;
					q.add(new int[] { nx, ny });
				}
			}
			time += 1;
			// 잡아먹을 수 있는 물고기가 존재한 경우 
			if(tx != n && ty != n) {
				// 해당 물고기가 위치한 맵은 0이 되고 상어의 좌표는 물고기의 좌표로 갱신된다.
				map[tx][ty] = 0;
				sx = tx; sy = ty;
				// 잡아먹은 숫자를 1 증가 시킨다.
				c += 1;
				// 잡아먹은 물고기의 숫자가 자신의 크기 만큼 이면
				if(c == s) { 
					// 자신의 크기를 1 증가 시키고
					s += 1;
					// 잡아먹은 물고기의 개수를 초기화한다.
					c = 0;
				}
				// 해당 물고기가 있는 곳까지 이동하는데 소요된 시간 만큼을 전체 이동시간에 더한다.
				total += time;
				return true;
			}
		}
		// 물고기를 잡아먹지 못한 경우
		return false;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		s = 2;

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 9) {
					sx = i;
					sy = j;
					map[i][j] = 0;
				}
			}
		}

		while(bfs()) {}
		System.out.println(total);
	}
}