[백준/Java] 2589: 보물섬

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

 

조건

• TimeLimit = 1s
• 상하좌우 이동만 가능하고, 한 칸 이동하는데 한 시간 소요됨
• 육지(L), 바다(W)중에 육지로만 이동 가능
• 두 지점을 이동하는데 걸리는 최단 시간중, 최댓값은?

 

풀이

1. BFS
   • 최단시간을 구해야하므로 BFS를 사용한다
   • 이때 최단시간들중 최댓값을 구하는 것이므로, 매번 최대시간을 초기화해주자
   • 출발점은 모든 'L'로 전체를 탐색한다

• 참고로 BFS의 TimeLimit은 다음처럼 구한다
  • 상하좌우로 움직일 수 있으므로, 시작점부터 전체를 탐색하는 경우 간선 E = 4*n*m이다
  • 이때 모든 지점을 탐색한다면, 전체 순회는 모든 Node의 수와 같으므로 V = n*m이다
  • 따라서 BFS의 전체 탐색은 O(4*(n*m)*(n*m)) ~= O(V^2)이다

 

코드

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


public class Main {

	static StringTokenizer st;
	static int r;
	static int c;
	static boolean[][] visited;
	static int[][] mapp;
	static int maxTime = 0;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	
	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
				
		mapp = new int[r][c];
		for (int i=0; i<r; i++) {
			
			String row = br.readLine();

			for (int j=0; j<c; j++) {
				
				Character s = row.charAt(j);
				mapp[i][j] = s == 'W' ? 0 : 1;
			
			}
			
		}
		
		// bfs
		for (int i=0; i<r; i++) {
			for (int j=0; j<c; j++) {
				
				if (mapp[i][j] == 0) continue;
				
				visited = new boolean[r][c];
				bfs(new Node(i, j, 0));
				
			}
		}
		
		// result
		System.out.print(maxTime);
		
	}
	
	
	
	static void bfs(Node stt) {
		
		Deque<Node> q = new ArrayDeque<>();
		q.add(stt);
		visited[stt.r][stt.c] = true;
		
		while (!q.isEmpty()) {
			
			Node cur = q.pop();			
			
			// 상하좌우 탐색
			for (int i=0; i<4; i++) {
				
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				
				if (!(0<=nr && nr<r) || !(0<=nc && nc<c)) continue;
				if (visited[nr][nc]) continue;
				if (mapp[nr][nc] == 0) continue;
				
				visited[nr][nc] = true;
				q.add(new Node(nr, nc, cur.t+1));
				maxTime = Math.max(maxTime, cur.t+1);
				
			}	
		}	
	}
	
	
	
	static class Node {
		
		int r;
		int c;
		int t;
		
		Node(int r, int c, int t) {
			this.r = r;
			this.c = c;
			this.t = t;
		}
		
	}
	
	
	
}