[문제] 백준 16236번 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

내 풀이

 

여기서의 포인트는 bfs를 이용해서 최단거리를 구하는 것이다.

처음에 거리를 구할 때 원래 거리 구하던 방식이었던 dfs로 해보니 계속 엉뚱한 답이 나왔었다.

bfs, dfs를 이용해 최단거리 구하는 방법 꼭 익힐 것!!

public class BOJ_16236 {
	static int N, sharkW = 2, sharkX, sharkY; // 상어 무게, 현재 상어 좌표
	static int[][] map;
	static int time = 0, dist, prey = 0; // 걸리는 시간, 거리, 먹은 물고기 수

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());

		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 9) { // 상어 위치
					sharkX = i;
					sharkY = j;
					map[i][j] = 0;
				}
			}
		}

		// 상어가 물고기 먹을 수 있을 때 까지 반복
		boolean flag = true;
		while (flag) {
			flag = canEat();
		}
		System.out.println(time);
	}

	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	// (sharkX, sharkY)-> (tx, ty) 로 이동하는 *최소 거리* 구하기
	static void getDist(int tx, int ty, boolean[][] visited) {

		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { sharkX, sharkY, 1 }); // x,y좌표랑 depth 저장
		visited[sharkX][sharkY] = true;

		while (!q.isEmpty()) {
			int[] curr = q.poll();

			for (int d = 0; d < 4; d++) {
				int nx = curr[0] + dx[d];
				int ny = curr[1] + dy[d];
				int nd = curr[2] + 1;
				// 조건: 배열 내에 위치 && 아직 방문 x && 상어 무게 보다 같거나 작을 때 이동 가능
				if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && map[nx][ny] <= sharkW) {
					visited[nx][ny] = true;
					q.offer(new int[] { nx, ny, nd });
				}
			}
			// 먼저 도착한게 최단 거리
			if (visited[tx][ty]) {
				dist = curr[2];
				break;
			}
		}
	}

	// 물고기 먹으러 가는 함수: 먹을 수 있으면 true, 없으면 false
	static boolean canEat() {
		int minD = Integer.MAX_VALUE;	// 최소거리
		int minX = N, minY = N;			// 최소거리일 때의 좌표
		boolean isFound = false;		// 물고기 찾았는지
		
		// 가장 가까운 한마리 정하기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if ((i == sharkX && j == sharkY) || map[i][j] == 0)	// 상어 위치이거나 물고기가 없으면 continue
					continue;

				if (map[i][j] < sharkW) { // 먹을 수 있는 후보: 상어무게보다 작을 때
					dist = 0; // dist 0으로 초기화
					getDist(i, j, new boolean[N][N]); // 거리 구하기

					if (dist == 0) // 이동 못함-> continue
						continue; 
					else { // 이동 가능
						isFound = true; // 하나라도 찾으면 true
						// 우선순위: 가장 가까이 있음 > 가장 위에 > 가장 왼쪽
						if (dist < minD) {
							minD = dist;
							minX = i;
							minY = j;
						} else if (dist == minD) {
							if (i < minX) {
								minX = i;
								minY = j;
							} else if (i == minX) {
								if (j < minY) {
									minY = j;
								}
							}
						}
					}
				}
			}
		}
		// 위에서 물고기 찾으면,
		if (isFound) {
			time += minD; // 소요 시간 갱신: 최소 거리만큼 더해준다.
			sharkX = minX; // 현재 상어 위치 갱신: 해당 물고기 위치로 이동
			sharkY = minY; 
			map[sharkX][sharkY] = 0;// 먹었으니까 0
			prey++;	// 물고기 먹은 수 ++
			// 상어 무게만큼 먹이 먹었으면 무게 하나 증가, 먹은 물고기 수 0으로 초기화
			if (prey == sharkW) {
				prey = 0;
				sharkW++;
			}
		}
		return isFound;
	}
}