[BAEKJOON_2589 - JAVA] 보물섬

문제

www.acmicpc.net/problem/2589

2589번: 보물섬

 

 

풀이

• 보물의 위치를 정하는 것이 낯선 문제였다.
  최단 거리로 이동하는데 가장 긴 시간이 걸리는 곳 → 최단, 최소가 들어간 경우 BFS를 활용한다는 생각
• 육지인 경우 BFS를 활용한 탐색.
• BFS를 사용한 최단거리 중 최댓값을 구하는 처음 접하는 문제였다.
  (최단거리 중 최댓값)
• 문제 난이도는 평이한 것으로 느껴졌다.

 

 

과정

1. Pos (row, col, 이동횟수) class를 만들어 활용.
2. map을 탐색하며, 육지인 경우 BFS로 탐색.
3. 범위는 isIn 함수를 만들어 사용.
   → 가독성을 높이기 위해 평소 함수로 뺀다.
4. 이동을 할 때마다, 기존의 최대 이동거리보다 큰 경우 갱신.
   → ret = Math.max 부분

 

 

알고리즘 지식

• BFS

 

 

JAVA코드

 package BaekJoon_2020_12_22__23;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @packageName : BaekJoon_2020_12_22
 * @fileName : BJ_2589_보물섬.java
 * @author : Mingeon
 * @date : 2020. 12. 23.
 * @language : JAVA
 * @classification : BFS
 * @time_limit : 1sec
 * @required_time : 00:40 ~ 01:22
 * @submissions : 1
 * @description 
 * 1. 최단 거리로 이동하는 bfs 탐색중 가장큰 값 구하기
 */

public class BJ_2589_보물섬 {

	static int height; // 보물섬 지도 높이
	static int width; // 보물섬 지도 너비
	static char[][] map; // 보물섬 지도
	static boolean[][] visited; // 방문 관리

	// 4방 탐색
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int minTime; // 최소 이동 시간

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		height = Integer.parseInt(st.nextToken());
		width = Integer.parseInt(st.nextToken());
		map = new char[height][width];
		minTime = 0;

		for (int i = 0; i < height; i++) {
			map[i] = br.readLine().toCharArray();
		} // End of input

		// bfs 최대값 탐색
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {

				if (map[i][j] == 'L') {
					visited = new boolean[height][width];
					int time = bfs(new Pos(i, j, 0));
					minTime = Math.max(minTime, time);
				}
			}
		}

		System.out.println(minTime);
		br.close();
	}

	private static int bfs(Pos pos) {
		int ret = 0;
		Queue<Pos> q = new LinkedList<Pos>();
		q.add(pos);
		visited[pos.row][pos.col] = true;

		while (!q.isEmpty()) {
			Pos p = q.poll();
			for (int d = 0; d < 4; d++) {
				int nextRow = p.row + dy[d];
				int nextCol = p.col + dx[d];

				// 범위 && 방문 && 육지 확인
				if (isIn(nextRow, nextCol) && !visited[nextRow][nextCol] && map[nextRow][nextCol] == 'L') {
					visited[nextRow][nextCol] = true; // 방문 표시
					q.add(new Pos(nextRow, nextCol, p.cnt + 1));
					ret = Math.max(ret, p.cnt + 1);
				}

			}
		}

		return ret;

	}

	// 범위검사
	private static boolean isIn(int row, int col) {
		if (row < 0 || row >= height || col < 0 || col >= width) {
			return false;
		}
		return true;
	}
}

class Pos {
	int row;
	int col;
	int cnt;

	public Pos(int row, int col, int cnt) {
		this.row = row;
		this.col = col;
		this.cnt = cnt;
	}

}