[알고리즘 / 백준] 2589 - 보물섬

www.acmicpc.net/problem/2589

2589번: 보물섬

 

문제는 위와 같으며, 이 문제는 BFS 와 Deque 를 사용하여 해결하였습니다.

 

먼저 모든 땅에 대하여 시작 땅부터 가장 멀리 떨어져 있는 땅까지의 최단 거리를 구한 뒤, 그 값과 기존에 구한 가장 먼 두 섬 사이의 거리와 비교하여 더 먼 값을 출력하는 방식으로 문제를 해결할 수 있습니다.

 

가장 멀리 떨어져 있는 땅까지의 최단 거리는 deque 를 사용하는 BFS 방식으로 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다. 이 문제에서 시간 초과를 피하기 위해 Pypy3 로 답을 제출하였습니다.

from sys import stdin
from collections import deque

# 상하좌우 이동할 수 있는 위치 값 저장
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# 시작 땅부터 가장 멀리 떨어진 땅까지의 최단 시간 구하기
def bfs(x, y):
    count = [[-1] * m for _ in range(n)]  # 땅까지 이동하는데 걸리는 시간 저장 (방문하지 않았기 때문에 걸린 시간 -1)
    queue.append([x, y])  # 시작 땅을 큐에 저장
    count[x][y] = 0  # 처음 시작 땅까지 이동하는데 걸리는 시간은 0으로 처리 (방문은 했지만 걸린 시간은 0)
    num = 0  # 가장 먼 땅까지 걸리는 최단 시간 저장

	# 더 이상 이어지는 땅이 없을 때까지 반복하며
    while queue:
        cx, cy = queue.popleft()  # 큐의 앞에서부터 차례대로 땅의 위치를 꺼내

		# 상하좌우 방향을 확인하면서
        for d in range(4):
            nx = cx + dx[d]
            ny = cy + dy[d]

            if 0 <= nx < n and 0 <= ny < m:  # 다음 위치가 지도 내에 위치하고
                if island[nx][ny] == 'L' and count[nx][ny] == -1:  # 다음 위치가 땅이면서 아직 방문하지 않은 경우
                    count[nx][ny] = count[cx][cy] + 1  # 다음 위치 땅까지 방문하는데 걸리는 시간 저장 (현재 땅까지 방문한 시간 + 1)
                    num = max(num, count[nx][ny])  # 지금까지 구한 가장 먼 땅까지 걸리는 시간과 다음 땅까지 가는데 걸리는 시간 중 더 큰 값을 저장
                    queue.append([nx, ny])  # 다음 위치 땅도 이어진 땅이므로 큐에 저장

    return num  # 최종적으로 가장 먼 땅까지 걸리는 시간 반환


n, m = map(int, stdin.readline().split())  # 지도의 높이, 너비 저장
island = [stdin.readline().strip() for _ in range(n)]  # 땅, 바다 위치 저장
queue = deque()  # deque 선언 (이어진 땅 저장)

time = 0

for i in range(n):
    for j in range(m):
        if island[i][j] == 'L':  # 지도 내 모든 땅에 대해서 
            time = max(time, bfs(i, j))  # 해당 땅과 가장 멀리 떨어진 땅까지 가는데 걸리는 시간 중 최대를 저장

print(time)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    private static int n;
    private static int m;

    private static String[] island;
    private static Deque<int[]> deque = new ArrayDeque<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 보물섬 지도의 높이, 너비 입력 받기
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 땅과 바다 위치 입력 받기
        island = new String[n];
        for (int i = 0; i < n; i++) {
            island[i] = br.readLine();
        }

        int time = 0;  // 가장 먼 섬까지 가는데 걸리는 최대 시간 저장 (정답)

        // 전체 지도를 확인하면서
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (island[i].charAt(j) == 'L') {  // 땅인 경우
                    // 해당 땅과 연결된 가장 먼 땅까지 가는데 걸리는 시간 구하기
                    time = Math.max(time, bfs(i, j));
                }
            }
        }

        System.out.println(time);
    }

    private static int bfs(int x, int y) {
        int[][] count = new int[n][m];  // 해당 땅을 몇 시간만에 방문했는지 저장
        deque.add(new int[]{x, y});  // 처음 시작 땅의 위치를 큐에 저장
        count[x][y] = 1;  // 처음 시작하는 위치를 방문한 것으로 우선 처리
        int num = 0;  // 가장 먼 땅까지 가는데 걸리는 시간

        while (!deque.isEmpty()) {
            int[] current = deque.pollFirst();

            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (island[nx].charAt(ny) == 'L' && count[nx][ny] == 0) {  // 땅이면서 아직 방문하지 않은 경우
                        count[nx][ny] = count[current[0]][current[1]] + 1;  // 다음 위치까지 이동한 시간 저장 (현재 위치까지 이동한 시간 + 1)
                        num = Math.max(num, count[nx][ny]);  // 이동 시간의 최대 값 저장
                        deque.add(new int[]{nx, ny});  // 다음 위치를 큐에 저장하기
                    }
                }
            }
        }

        return num - 1;  // 처음 방문한 땅의 값도 추가되었으므로 제거
    }
}