[BOJ] 2586: 보물섬 (JAVA)

2589번: 보물섬

 

틀린 이유

 

보물이 묻혀있는 곳은 육지의 땅과 땅 사이의 가장 먼 거리이다.

이는 "L"이 갈 수 있는 곳 중에서 가장 먼 곳을 뜻한다.

그럼 각 정점(L)마다 갈 수 있는 최장거리를 구하면 된다.

 

내가 간과한 것은 새로운 정점을 탐색할 때 마다 방문 초기화를 해줘야 한다는 것이었다.

왜냐하면 이미 첫번째 정점을 찾고 난 다음에는 모든 "L"은 true처리가 되어있기 때문에, 이후 BFS를 진행할 수 없다.

매 정점마다 초기화를 해주어야 모든 정점에서의 최장거리를 구할 수 있음.

 

 

 

반례

7 7
LLLLLLL
LLLLLLW
LLLLLWW
LLLLLWW
LLLWWWW
LLWWWWW
LWWWWWW
Output: 7
Answer: 12

 

이 반례덕분에 해결한 것은 아니지만, 내 코드에 오류가 있다는 사실을 발견하게 해줬습니다 ~! 💫

 

 

package 백준renew;

import java.io.*;
import java.util.*;

public class 골드5_2589_보물섬 {
	static int N, M, count;
	static String map[][];
	static boolean visited[][];
	static int goX[] = {-1, 1, 0, 0};
	static int goY[] = {0, 0, -1, 1};
	static class Treasure{
		int x;
		int y;
		int cnt;
		Treasure(int x, int y, int cnt){
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	public static void main(String[] args) throws Exception{
		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 String[N][M];
		visited = new boolean[N][M];
		
		for(int i=0; i<N; i++) {
			String tmp = br.readLine();
			for(int j=0; j<M; j++) {
				map[i][j] = tmp.charAt(j)+"";
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				visited = new boolean[N][M];
				if(map[i][j].equals("L") && !visited[i][j]) {
					BFS(i, j, 0);
				}
			}
		}
		
		System.out.println(count);
	}
	static void BFS(int x, int y, int cnt) {
		Queue<Treasure> queue = new LinkedList<>();
		queue.offer(new Treasure(x, y, cnt));
		
		while(!queue.isEmpty()) {
			Treasure t = queue.poll();
			visited[t.x][t.y] = true;
			
			for(int i=0; i<4; i++) {
				int newX = t.x + goX[i];
				int newY = t.y + goY[i];
				
				if(newX <0 || newX >= N || newY <0 || newY >= M || map[newX][newY].equals("W") || visited[newX][newY]) {
					continue;
				}
				
				count = Math.max(count, t.cnt+1);
				queue.offer(new Treasure(newX, newY, t.cnt+1));
				visited[newX][newY] = true;
			}
		}
	}
}