[2589] 보물섬 - Java[자바]

 

 

| 문제 링크

 

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

2589번: 보물섬

 

 

 

 

---

 

 

 

 

 

| 문제

 

1. 이차원 배열로 W:바다, L:육지 두 가지 값이 주어집니다.(행렬 최대 길이 50)
2. 보물은 육지에만 존재하며, 육지에서 최단 경로로 갈 수 있는 가장긴 시작점과 끝점에 보물이 묻혀있습니다.
3. 이차원 배열로 지도가 주어졌을 때, 보물이 묻혀 있는 두 곳 사이의 최단 경로 시간(1칸당 1시간)을 출력하시오.

 

 

 

 

---

 

 

 

 

 

| 풀이

 

1. 행렬이 50x50으로 육지마다 bfs를 동작해도 시간초과되지 않습니다.
2. 우선 bfs 메서드를 만듭니다.
   Queue는 int[] 배열로 파라미터는 {row,col,count} 세 가지를 사용합니다.
   해당 좌표로부터 4방 탐색을하며 아래의 조건 중 하나라도 걸리는 경우 해당 탐색을 종료(continue)합니다.
   1) 배열의 범위를 벗어난 경우
   2) 바다(W)를 만난 경우
   3) 이미 방문한 육지인 경우
3. 조건에 포함되지 않는 경우 해당 육지는 방문처리 해주며, count+1과 max를 비교해 더 큰 값을 max로 할당해줍니다.
4. 2중 for문으로 map을 탐색하며, 육지가 나온 경우 2번에서 만든 bfs를 동작해 모든 육지에 대해 방문을 완료 후 max값을 출력해줍니다.

 

 

 

---

 

 

 

 

 

| 코드

 

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static char[][] map;
	public static boolean[][] flag;
	public static int row, col;
	public static int max;
	public static int[][] delta = {{-1,0},{0,1},{1,0},{0,-1}};

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		row = Integer.parseInt(st.nextToken());
		col = Integer.parseInt(st.nextToken());
		
		//배열로 입력값을 받음
		map = new char[row][col];
		for(int r = 0; r<row; r++) {
			String str = br.readLine();
			for(int c = 0; c<col; c++) {
				map[r][c] = str.charAt(c);
			}
		}
		
		max = 0;
		//육지가 나올때마다 해당 좌표에 대해 bfs 동작
		for(int r = 0; r<row; r++) {
			for(int c = 0; c<col; c++) {
				if(map[r][c]=='L') {
					//육지마다 방문처리를 초기화
					flag = new boolean[row][col];
					//해당 육지는 방문처리
					flag[r][c] = true;
					bfs(r,c);
				}
			}
		}
		
		bw.write(String.valueOf(max));
		br.close();
		bw.close();

	}
	
	public static void bfs(int r, int c) {
		Queue<int[]> que = new LinkedList<>();
		que.add(new int[] {r,c,0});
		
		while(!que.isEmpty()) {
			int[] now = que.poll();
			for(int i = 0; i<4; i++) {
				int dr = now[0] + delta[i][0];
				int dc = now[1] + delta[i][1];
				
				//사방 탐색이 배열의 범위를 벗어나거나, 바다이거나, 이미 방문한 육지인 경우 continue
				if(dr<0 || dr>=row || dc<0 || dc>=col || map[dr][dc]=='W' || flag[dr][dc])
					continue;
				
				flag[dr][dc] = true;
				
				max = Math.max(max,now[2]+1);
				que.add(new int[] {dr,dc,now[2]+1});
			}
		}
	}

}