[백준/java] 2589번: 보물섬 - BFS, 브루트포스

2589번: 보물섬

 

728x90

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

2589번: 보물섬

 

2589번: 보물섬

 

브루트 포스와 BFS 탐색이 결합된 문제이다.

 

처음에 어떻게 보물의 위치를 구해야하나 싶었지만

 

같이 풀은 친구의 힌트로 두 점의 위치를 구할 필요가 없다.(브루트 포스라서!)

 

반응형

이중 for문으로 무차별 대입을 해줘서

step이 가장 큰, 즉 두 점 사이의 거리가 가장 큰 값을 반환하면 된다.

두 점 사이의 거리가 가장 먼 곳이 보물의 위치이기 때문에,

그냥 거리값만 반환하면 된다.

 

package 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 TreasureLand {
	static char[][] map;
	static boolean[][] visit;
	static int[] dy = {1, 0, -1, 0};
	static int[] dx = {0, 1, 0, -1};
	static int N, M;
	static class Node {
		int y,x, step;
		public Node(int y, int x, int step) {
			this.y = y;
			this.x = x;
			this.step = step;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, 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];
		visit = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		
		System.out.println(bfs());
	}
	
	public static int bfs() {
		int len = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j] == 'W') continue;
				int cnt = 0;
				
				Queue<Node> q = new LinkedList<Node>();
				q.add(new Node(i, j, 0));
				while(!q.isEmpty()) {
					Node cur = q.poll();
					
					if(visit[cur.y][cur.x]) continue;
					visit[cur.y][cur.x] = true;
					
					for (int dir = 0; dir < 4; dir++) {
						int ny = cur.y + dy[dir];
						int nx = cur.x + dx[dir];
						
						if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
						if(visit[ny][nx] || map[ny][nx] == 'W') continue;
						
						int step = cur.step + 1;
						cnt = step;
						q.add(new Node(ny, nx, step));
					}
				}
				
				visit = new boolean[N][M];
				len = Math.max(len, cnt);
			}
		}
		
		return len;
	}
}