[백준] 보물섬 2589 [JAVA]

출처 : www.acmicpc.net/problem/2589

2589번: 보물섬

문제

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

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

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

입력

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

출력

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

풀이

 - BFS 

 - 처음부터 끝까지 돌며, L로 시작하는 점을 각 시작점으로 두고 돌아가지 않으며, 최장 거리를 구한다.

 - 각 시작점 마다 방문처리를 어떻게 해야할지 고민 됐다.

 - 각 시작점을 visit 으로 갖는 3차원 배열을 만들어서 해결했다.

 - 맵의 크기가 작아서 망정이지, 컸다면 다른 방법을 강구했어야 할것이다.

코드

package 알고리즘공부하기;

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 보물섬_2589 {

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static char[][] map;
	static int N, M; // N = Row , M = column;
	static int island_count = 0;
	static boolean[][][] visited;
	
	public static class island{
		int r;
		int n;
		int count;
		public island(int r, int n, int count) {
			this.r = r;
			this.n = n;
			this.count = count;
		}
		
	}
	public static int execute() {
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int answer = Integer.MIN_VALUE;
		Scanner sc = new Scanner(System.in);
		// 구현하세요.
		
		N = sc.nextInt();
		M = sc.nextInt();

		// store
		map = new char[N][M];
		for (int i = 0; i < N; i++) {
			String temp = sc.next();
			for (int j = 0; j < M; j++) {
				map[i][j] = temp.charAt(j);
				if (map[i][j] == 'L')
					island_count++;
			}
		}
		// test
		//print();

		//
		visited = new boolean[island_count][N][M]; // 각 섬 을 출발지로 하는 방문배열
		int cur_count =0;
		for ( int i=0; i< N; i++) {
			for ( int j=0; j<M;j ++) {
				// 처음부터 끝까지 돌면서 육지를 발견했을 때를 시작점으로 최대갈 수 있는 곳 가보기
				if ( map[i][j] == 'L') {
					answer = Math.max(answer, bfs(i,j,0, cur_count));
					cur_count++;
				}
			}
		}
		return answer; // 리턴값을 수정하세요
	} // end of execute

	private static int bfs(int i, int j, int k, int visit_count) {
		// TODO Auto-generated method stub
		int maxcount =Integer.MIN_VALUE;
		
		Queue<island> queue = new LinkedList<>();
		visited[visit_count][i][j] = true; // 방문처리하고
		queue.add(new island(i,j,0));
		
		while ( !queue.isEmpty()) {
			
			island cur = queue.poll();
			maxcount = Math.max(maxcount, cur.count);
			for( int d=0; d<4; d++) {
				int nr = cur.r + dr[d];
				int nc = cur.n + dc[d];
				
				// 맵 안에 있고, 다음 갈 곳이 섬이면서, 방문하지 않았다면?!
				if ( isIn(nr,nc) && map[nr][nc] == 'L' && !visited[visit_count][nr][nc]) {
					// 방문처리하고
					visited[visit_count][nr][nc] = true; 
					// 전진하자
					queue.add(new island(nr, nc, cur.count+1));
				}
			}
			
		}
		return maxcount;
	}

	private static boolean isIn(int nr, int nc) {
		// TODO Auto-generated method stub
		if ( nr >=0 && nr < N && nc >=0 && nc < M) return true;
		
		return false;
	}

	private static void print() {
		// TODO Auto-generated method stub
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) throws IOException {
		
		System.out.println(execute());
	}
} // end of class