[백준 2589] 보물섬

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

[입력]

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

[출력]

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

[예제입력]

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

[예제출력]

8

[문제풀이]

1. Point 클래스를 좌표 x, y 변수와 해당 육지 위치에서 bfs로 퍼져나갈 때의 값을 저장하기 위한 count변수도 같이 선언해준다.
2. 육지인 곳만 상하좌우로 움직일 수 있으므로 각각의 육지에서 시작해서 가장 거리가 먼 육지까지 탐색해야하므로 너비 우선 탐색(BFS)알고리즘을 이용한다.
3. 각각의 육지를 시작점으로 잡고 탐색을 끝내면 처음부터 다시 방문을 해야하므로 방문 배열을 초기화 해준다.
4. 해당 육지에서 거리가 가장 먼 육지를 찾아야 하므로 전역 변수 result값과 너비 우선 탐색으로 이동한 count변수와 더 큰 값을 result에 대입하여 모든 육지를 탐색하며 최종적으로 이동시간이 가장 오래걸린 result값을 출력해준다.
5. 그 후 지도 범위내에 있고 이동할 위치가 육지이고 방문했던 곳이 아니라면 해당 좌표를 큐에 넣어주면서 탐색을 진행한다.

[코드]

package com.day1017;

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

public class BOJ2589 {
	
	static class Point{	// 1.
		int x, y, count;

		public Point(int x, int y, int count) {
			this.x = x;
			this.y = y;
			this.count = count;
		}
		
	}
	static int N, M;
	static char[][] map;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int cnt;
	static int tmp;
	static int result;
	
	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 char[N][M];
		
		
		for(int i=0; i<N; i++) {
			String s = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = s.charAt(j);
			}
		}	//입력완료
		
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 'L') {
					visited = new boolean[N][M];	// 3.
					bfs(i, j);	// 2.
					
				}
			}
		}
		System.out.println(result);
	}

	private static void bfs(int r, int c) {
		Queue<Point> q = new ArrayDeque<>();
		q.add(new Point(r, c, 0));
		
		while(!q.isEmpty()) {
			Point cur = q.poll();
			int x = cur.x;
			int y = cur.y;
			result = Math.max(result, cur.count);	// 4.
			
			visited[x][y] = true;
			
			
			for(int k=0; k<4; k++) {
				int nx = x+dx[k];
				int ny = y+dy[k];
				
				if(nx >= 0 && ny >=0 && nx < N && ny < M && map[nx][ny] == 'L') {
					if(!visited[nx][ny]) {
						visited[nx][ny] = true;	// 5.
						q.add(new Point(nx, ny, cur.count+1));	// 5.
						
					}
				}
			}
		}
		
	}

}