2589_보물섬

사용 알고리즘: bfs? 다익스트라?

사용 언어: java

 

package week34;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main_bj_2589_보물섬 {
	static int n,m, map[][], answer, DP[][];
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};

	public static void main(String[] args) throws IOException {
		init_2589();
		
		boolean[][] bf = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(map[i][j]==1 && !bf[i][j]) {
					bf[i][j] = true;
					bfs_2589(i, j);
				}
			}
		}
		
		System.out.println(answer);
	}

	private static void bfs_2589(int x, int y) {
		int[][] dp = new int[n][m];
		for (int i = 0; i < n; i++) {
			Arrays.fill(dp[i], Integer.MAX_VALUE);
		}
		dp[x][y] = 0;
		
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {x, y, 0});
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			
			for (int d = 0; d < 4; d++) {
				int nx = p[0] + dx[d];
				int ny = p[1] + dy[d];
				
				if(inMap(nx, ny) && dp[nx][ny] > p[2]+1 && map[nx][ny]==1) {
					dp[nx][ny] = p[2]+1;
					q.add(new int[] {nx, ny, p[2]+1});
				}
			}
		}
		
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < m; j++) {
				if(dp[i][j]!=Integer.MAX_VALUE && dp[i][j] > answer) answer = dp[i][j];
			}
		}
	}

	private static void init_2589() 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 int[n][m];
//		DP = new int[n][m]; //큰 수로 갱신.!
		
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				if(s.charAt(j) == 'L')
					map[i][j] = 1;
			}
		}
	}

	private static boolean inMap(int x, int y) {
		if(x>=0&&x<n && y>=0&&y<m) return true;
		return false;
	}
}

 

문제가 참 이해하기 어렵게 쓰여 있다ㅎㅎ...

결국 같은 덩어리에 있는 육지(L) 중에서, 가장 멀리 떨어져 있는 거리를 구하라는 것이다..

 

어디가 육지의 끝인지 알 수 없기 때문에

각 지점마다 bfs를 돌려서, 가장 멀리 있는 곳을 찾으면 되겠다고 생각했다.

 

그래서 bfs를 돌릴 때마다 dp를 새로 만들어서, dp 값 중 가장 큰 값으로 갱신한다.

(dp를 int의 최대값으로 설정했기 때문에, 당연히 dp[i][j]가 int의 최대값이 아닐 때만 값을 비교해서 갱신한다)