[백준] 2589 - 보물섬

1. 문제

2589번: 보물섬

2. 개요

각 칸마다 육지, 바다로 표시되어있는 보물 지도가 있다.

이동은 상하좌우 이웃된 육지 한 칸으로만 가능하며, 한 칸 이동에는 한 시간이 걸린다.

보물은 서로간에 최단 거리로 이동하는 데 있어 가장 오랜 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.

이 때 보물이 있는 두 육지 두 곳 간의 최단거리를 이동하는데 걸리는 시간을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

지도에 있는 모든 육지에 대해 BFS를 실행한다.

이 때, BFS를 실행할 때마다 visited배열을 초기화해준다.

visited 배열의 값은 1씩 늘려주면서 소요되는 최단시간을 확인할 수 있도록 한다.

한 위치에서의 BFS가 완료될 때마다 소요되는 최단시간중의 최댓값을 리턴한다.

리턴된 값과 현재까지 저장된 답 중 큰 값으로 답을 갱신한다.

지도의 모든 좌표에 대해 탐색 및 BFS가 완료되었다면 답을 출력한다.

3-2. Python

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
answer = 0

board = []

for i in range(N):
    board.append(list(sys.stdin.readline().rstrip()))

def BFS(y, x):
    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

    visited = [[-1 for i in range(M)] for j in range(N)]
    q = deque([[y, x]])
    visited[y][x] = 0

    maxValue = 0

    while q:
        nowY, nowX = q.popleft()

        for i in range(4):
            nextY, nextX = nowY + dirY[i], nowX + dirX[i]

            if nextY < 0 or nextY >= N or nextX < 0 or nextX >= M:
                continue

            if board[nextY][nextX] != "L":
                continue

            if visited[nextY][nextX] != -1:
                continue

            visited[nextY][nextX] = visited[nowY][nowX] + 1
            maxValue = visited[nextY][nextX]
            q.append([nextY, nextX])

    return maxValue

for i in range(N):
    for j in range(M):
        if board[i][j] == 'L':
            answer = max(answer, BFS(i, j))

print(answer)

3-3. C#

namespace boj_2589
{
    internal class Program
    {
        static int N;
        static int M;
        static char[,] board;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            int answer = 0;
            board = new char[N, M];

            for (int i = 0; i < N; i++)
            {
                string row = sr.ReadLine();
                for (int j = 0; j < M; j++)
                {
                    board[i, j] = row[j];
                }
            }

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (board[i, j] == 'L')
                        answer = (int)MathF.Max(answer, BFS(i, j, N, M));
                }
            }

            sw.WriteLine(answer);
            sw.Close();
        }

        static int BFS (int y, int x, int r, int c)
        {
            int[] dirY = { -1, 0, 1, 0 };
            int[] dirX = { 0, -1, 0, 1 };

            int maxValue = 0;
            int[,] visited = new int[r, c];

            Queue<int[]> q = new();
            q.Enqueue(new int[] { y, x });
            visited[y, x] = 1;

            while (q.Count > 0)
            {
                int[] now = q.Dequeue();
                int nowY = now[0];
                int nowX = now[1];

                for (int i = 0; i < 4; i++)
                {
                    int nextY = nowY + dirY[i];
                    int nextX = nowX + dirX[i];

                    if (nextY < 0 || nextY >= r || nextX < 0 || nextX >= c)
                        continue;

                    if (board[nextY, nextX] != 'L')
                        continue;

                    if (visited[nextY, nextX] != 0)
                        continue;

                    visited[nextY, nextX] = visited[nowY, nowX] + 1;
                    maxValue = visited[nextY, nextX] - 1;
                    q.Enqueue(new int[] { nextY, nextX });
                }
            }

            return maxValue;
        }
    }
}