[백준/JAVA] BOJ 2589 - 보물섬

👀 문제

2589번: 보물섬 ✨ 골드 5

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

🔑 키포인트

너비 우선 탐색 브루트포스 알고리즘 백트래킹

✍️ 코드

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

public class BOJ2589 {
	static int n;
	static int m;
	static int[][] graph;
	static int[][] temp_graph;
	static ArrayList<int[]> sea;
	static Queue<int[]> queue;
	static int dist;

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

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		graph = new int[n][m];
		temp_graph = new int[n][m];
		queue = new LinkedList<int[]>();
		sea = new ArrayList<int[]>();

		int answer = 0;

		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			for (int j = 0; j < m; j++) {
				// L: 육지, W: 바다
				if (str.charAt(j) == 'L') {
					graph[i][j] = 0;
					temp_graph[i][j] = 0;
				} else {
					graph[i][j] = -1;
					temp_graph[i][j] = -1;
					sea.add(new int[] { i, j });
				}
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (graph[i][j] == 0) {
					queue.offer(new int[] { i, j });
					bfs(i, j);
					dist = 0;
					for (int k = 0; k < n; k++) {
						for (int l = 0; l < m; l++) {
							dist = Math.max(dist, temp_graph[k][l]);
						}
					}
					answer = Math.max(answer, dist);
				}
			}
		}

		System.out.println(answer-1);
	}

	public static void bfs(int i, int j) {
		int[] dx = { -1, 1, 0, 0 };
		int[] dy = { 0, 0, -1, 1 };
		
		temp_graph = new int[n][m];
		temp_graph[i][j] = 1;

		for (int[] s : sea) {
			temp_graph[s[0]][s[1]] = -1;
		}

		while (!queue.isEmpty()) {
			int[] now = queue.poll();
			int x = now[0];
			int y = now[1];

			for (int k = 0; k < 4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];

				if (0 <= nx && nx < n && 0 <= ny && ny < m) {
					if (temp_graph[nx][ny] == 0) {
						temp_graph[nx][ny] = temp_graph[x][y] + 1;
						queue.offer(new int[] { nx, ny });
					}
				}
			}
		}

	}
}