백준 2589 보물섬(JAVA 자바)

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

2589번: 보물섬

문제

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

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

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

 

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

 

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

 

문제 유형

BFS

 

코드

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

public class BJ2589_보물섬 {
	static int map[][];
	static boolean visited[][];
	static int N, M, res;
	static Queue<Data> q;

	static class Data {
		int r;
		int c;
		int cnt;

		public Data(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
	}

	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };
	
	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());
		map = new int [N][M];
		visited = new boolean [N][M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for (int j = 0; j < M; j++) {
				char c = str.charAt(j);
				if(c == 'W') { // 바다라면 map에 0으로 들어감
					map[i][j] = 0;
				}else { // 육지라면 map에 1로 들어감
					map[i][j] = 1;
				}
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited = new boolean[N][M];
				if(map[i][j] == 1 && !visited[i][j]) {
					findTreasure(i, j);
				}
			}
		}
		
		System.out.println(res);
	}
	
	public static  void findTreasure(int cR, int cC) {
		q = new LinkedList<>();
		visited[cR][cC] = true;
		q.add(new Data(cR, cC, 0));
		
		Data cur = null;
		while(!q.isEmpty()) {
			cur = q.poll();
			if(cur.cnt > res) {
				res = cur.cnt;
			}
			
			for (int dir = 0; dir < 4; dir++) {
				int nR = cur.r + dr[dir];
				int nC = cur.c + dc[dir];
				
				if(nR < 0 || nC < 0 || nR >= N || nC >= M)
					continue;
				
				if(visited[nR][nC] || map[nR][nC] == 0)
					continue;
				
				visited[nR][nC] = true;
				q.add(new Data(nR, nC, cur.cnt + 1));
			}
		}
	}
}

최단 거리를 찾는 문제이므로 BFS로 풀었다. 

바다라면 W, 육지라면 L로 입력이 들어오는데 그냥 0과 1로 구분하여 map에 저장해주었다.

모든 육지를 돌아보면서 그 중에 제일 큰 값을 구하면 된다. 따라서 visited 배열을 계속 초기화해주면서 풀었다. 나는 객체를 계속 재할당했는데 그냥 fill로 false 해도 될 것 같다.