[백준] 16236번 - 아기상어

 

BFS문제에 다양한 조건을 달아서 푸는 문제이다. 문제 해결이 쉽지 않아서 다른 블로그들의 풀이를 읽으면서 풀이를 진행했다. 문제를 나누어서 생각해보면

 

1. 상어보다 작은 물고기가 있는 곳을 탐색하는 부분

2. 탐색 거리가 같을 경우 우선순위를 구분하는 부분

3. 상어의 크기와 먹은 물고기의 수를 변경/초기화 해주는 부분

 

이 3 부분을 신경써주면서 풀이하게 되면 문제를 해결할 수 있다. 문제 해결에 있어서는 아래의 블로그를 참고하여 풀이하였다. 문제에 대한 접근 방법이나 해설이 잘 되어 있어서 참고하기 좋았다.

https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-16236-%EC%95%84%EA%B8%B0-%EC%83%81%EC%96%B4#%EC%95%84%EA%B8%B0-%EC%83%81%EC%96%B4%EA%B0%80-%EB%AC%BC%EA%B3%A0%EA%B8%B0%EB%A5%BC-%EC%9E%A1%EC%95%84-%EB%A8%B9%EC%9D%84-%EC%88%98-%EC%9E%88%EB%8A%94-%EC%8B%9C%EA%B0%84%EC%9D%84-%EA%B5%AC%ED%95%98%EB%8A%94-%EB%AC%B8%EC%A0%9C

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class shark {
	int x;
	int y;

	shark(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class p16236 {
	public static int[][] ary;
	public static int[][] dist;

	public static int a;

	public static int[] nx = { -1, 0, 0, 1 };
	public static int[] ny = { 0, -1, 1, 0 };

	public static int min_x = Integer.MAX_VALUE;
	public static int min_y = Integer.MAX_VALUE;
	public static int min_dist = Integer.MAX_VALUE;

	public static int shark_x;
	public static int shark_y;
	public static int shark_size = 2;
	public static int shark_cnt = 0;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		a = Integer.parseInt(br.readLine());
		ary = new int[a][a];
		dist = new int[a][a];

		for (int i = 0; i < a; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < a; j++) {
				ary[i][j] = Integer.parseInt(st.nextToken());

				if (ary[i][j] == 9) {
					shark_x = i;
					shark_y = j;
					ary[i][j] = 0;
				}
			}
		}

		int rst = 0;

		for (;;) {
			init();

			bfs(shark_x, shark_y);

			if (min_x != Integer.MAX_VALUE && min_y != Integer.MAX_VALUE) {
				// 탐색을 정상적으로 했을 경우 해당 좌표까지의 이동 거리를 더해줌
				rst += dist[min_x][min_y];

				shark_cnt++;
				// 상어 크기 변경
				if (shark_cnt == shark_size) {
					shark_size++;
					shark_cnt = 0;
				}
				
				ary[min_x][min_y] = 0;

				shark_x = min_x;
				shark_y = min_y;
				//이동한 물고기가 있던 칸의 값을 변경하고 상어 위치를 변경
			} else {
				break;
			}
		}
		System.out.println(rst);
	}

	public static void bfs(int x, int y) {
		Queue<shark> q = new LinkedList<>();
		q.add(new shark(x, y));
		dist[x][y] = 0;// 현재 좌표의 거리

		while (!q.isEmpty()) {
			shark n = q.poll();
			x = n.x;
			y = n.y;

			for (int i = 0; i < 4; i++) {
				int X = x + nx[i];
				int Y = y + ny[i];

				if (X >= 0 && X < a && Y >= 0 && Y < a) {

					if (ary[X][Y] <= shark_size && dist[X][Y] == -1) {// 처음 방문하는 경우 갱신
						dist[X][Y] = dist[x][y] + 1;

						if (ary[X][Y] != 0 && ary[X][Y] < shark_size) {

							if (min_dist > dist[X][Y]) {// 최단거리를 구하는 갱신
								min_x = X;
								min_y = Y;
								min_dist = dist[X][Y];
							} else if (min_dist == dist[X][Y]) {
								if (min_x == X) {// 같은 개체가 존재할 경우 우선순위를 위에있고, 왼쪽에 있는 것으로 지정
									if (min_y > Y) {
										min_x = X;
										min_y = Y;
									}
								} else if (min_x > X) {
									min_x = X;
									min_y = Y;
								}
							}
						}
						q.add(new shark(X, Y));
					}
				}
			}
		}
	}

	public static void init() {
		min_x = Integer.MAX_VALUE;
		min_y = Integer.MAX_VALUE;
		min_dist = Integer.MAX_VALUE;

		for (int i = 0; i < a; i++) {
			for (int j = 0; j < a; j++) {
				dist[i][j] = -1;
			}
		}
	}
}