[백준][자바]2589 보물섬

왠만한 알고리즘 문제는 자바로 풀기로 결정했다

이번엔 bfs문제였는데 처음에 dfs로 진행했다가 계속 오류나 bfs로 진행했다

나는 두가지 방법이 도긴개긴이라고 생각했는데

마침 질문리스트에 비슷한 내용으로 올라왔는데

BFS는 최단거리를 찾자마자 종료할수 있기 때문이고..

DFS는 시작점에서 도착점으로 가는 거의 무한한 종류의 길을 모두 탐색해야한다더라...

라는 이야기..

여튼 이문제는 모든 구간에서 가장 많이 걸린시간을 답으로 출력하면되더라..

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class point {
	int x;
	int y;
	point(int y,int x){
		this.x = x;
		this.y = y ;
	}
	
}
public class backjoon_2589 {
	/*
	 * 
	 * 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 
	 * 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다.
	 *  각 칸은 육지(L)나 바다(W)로 표시되어 있다. 
	 *  이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 
	 *  한 칸 이동하는데 한 시간이 걸린다. 
	 *  보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 
	 *  육지 두 곳에 나뉘어 묻혀있다.
	 *   육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나,
	 *    멀리 돌아가서는 안된다.
	 */
	static String[][] map= new String[51][51];
	static boolean[][] visit = new boolean[51][51];
	static int N;
	static int M;
	//상 하 좌 우  1, -1, 0 , 0
	static int[] dx ={0,-1,0,1};
	static int[] dy= {-1,0,1,0};
	
	
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine();
		for (int i = 0 ; i < N; i++){
			String[] arr = sc.nextLine().split("");
			for (int j = 0; j < arr.length ; j++) {
				map[i][j] = arr[j]; 
				visit[i][j] = false;
			}
		}
		
		
		findWay();
	}
	
	public static void findWay(){
		int max= 0;
		for (int i = 0 ; i < N; i++){
			for (int j = 0; j < M ; j++) {
				
				if (map[i][j].equals("W"))
					continue;
				
				int temp = bfs(i,j);
				
				if( temp > max ) {
						max = temp;
				}
			}
		}
		System.out.println(max);
	}
	public static int bfs(int sero, int garo) {
		
		int cnt = -1;
		initBool();
		
		Queue q = new LinkedList();
		point p = new point(sero,garo);
		q.add(p);
		visit[sero][garo] = true;
		
		while(!q.isEmpty()) {
			
			cnt++;
			int qsize =q.size();  
			
			/*
			 * 반복을 q.size만큼 도는것은 맞지만, 
			 * 그 과정에서 큐에 추가되는것도 q.size에 반영되기 때문에의도와 다르게 동작합니다.
			 * 다른 변수에 따로 분리해서 반복해야합니다.
			 */
			
			for(int k = 0 ; k< qsize; k++) {
				
				point pt = q.poll();
				
				for(int i = 0 ; i< 4; i++) {
					int x = dx[i] + pt.x;
					int y = dy[i] + pt.y;
					if(y >= 0 && y < N && x >=0 && x < M ) {
						//지상이고 아직 한번도 안가본경우 
						if(map[y][x].equals("L") && !visit[y][x]) {
							q.add(new point(y,x));
							visit[y][x] = true;
						}
					}
				}
			}
		}
		return cnt;
		
	}
	
	public static void initBool() {
		for (int i = 0 ; i < N; i++){
			for (int j = 0; j < M ; j++) {
				visit[i][j] = false;				
			}
		}
	}

}