[백준] 3055 - 탈출

1. 문제

3055번: 탈출

2. 개요

물, 돌, 고슴도치, 비버의 굴이 있는 숲이 있다.

물은 매 분마다 인접한 칸으로 퍼지며 고슴도치 또한 매 분마다 인접한 칸으로 이동할 수 있다.

물은 비버의 굴에는 퍼지지 않으며, 고슴도치는 물이 있는 곳으로 이동할 수 없다.

또한 고슴도치는 바로 물이 퍼질 예정일 공간으로도 이동할 수 없다.

물과 고슴도치 모두 돌을 통과할 수 없다.

이 때 고슴도치가 비버의 굴 까지 이동할 수 있는 최소 시간을 구하는 문제.

이동 불가능하다면 KAKTUS를 출력한다.

3. 풀이 및 코드

3-1. 풀이

BFS를 이용하면 된다.

고슴도치가 물이 찰 예정인 공간으로는 이동할 수 없기에 물을 먼저 퍼지게 하고 고슴도치를 이동시키면 된다.

3-2. Python

import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())

visited = [[0 for i in range(C)] for j in range(R)]
forest = []
waters = deque()
hedgehog = deque()

for i in range(R):
    forest.append(list(sys.stdin.readline().rstrip()))

    for j in range(C):
        if forest[i][j] == '*':
            waters.append([i, j])
            visited[i][j] = -1

        elif forest[i][j] == 'S':
            hedgehog.append([i, j])
            visited[i][j] = 1

        elif forest[i][j] == 'D':
            dest = [i, j]

def waterbfs(q):
    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]
    tmpq = deque()

    while q:
        now = q.popleft()

        for i in range(4):
            nextY, nextX = now[0] + dirY[i], now[1] + dirX[i]

            if nextX < 0 or nextX >= C or nextY < 0 or nextY >= R:
                continue

            if forest[nextY][nextX] == 'X' or forest[nextY][nextX] == 'D':
                continue

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

            visited[nextY][nextX] = -1
            tmpq.append([nextY, nextX])

    return tmpq

def hedgehogbfs(q, count):
    dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]
    tmpq = deque()

    while q:
        now = q.popleft()

        for i in range(4):
            nextY, nextX = now[0] + dirY[i], now[1] + dirX[i]

            if nextX < 0 or nextX >= C or nextY < 0 or nextY >= R:
                continue

            if forest[nextY][nextX] == 'X' or forest[nextY][nextX] == '*':
                continue

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

            visited[nextY][nextX] = count
            tmpq.append([nextY, nextX])

    return tmpq

count = 1
while visited[dest[0]][dest[1]] == 0 and hedgehog:
    waters = waterbfs(waters)
    hedgehog = hedgehogbfs(hedgehog, count)
    count += 1

if visited[dest[0]][dest[1]] > 0:
    print(visited[dest[0]][dest[1]])

else:
    print('KAKTUS')

3-3. C#

using System.Diagnostics.CodeAnalysis;

namespace boj_3055
{
    internal class Program
    {
        static string[] input;
        static int R;
        static int C;
        static int[,] visited;
        static char[,] forest;

        static void Main(string[] args)
        {
            input = Console.ReadLine().Split();
            R = int.Parse(input[0]);
            C = int.Parse(input[1]);

            forest = new char[R, C];
            visited = new int[R, C];
            int[] dest = new int[2];
            Queue<int[]> waters = new Queue<int[]>();
            Queue<int[]> hedgehog = new Queue<int[]>();

            for (int i = 0; i < R; i++)
            {
                string row = Console.ReadLine();
                for (int j = 0; j < C; j++)
                {
                    forest[i, j] = row[j];

                    if (row[j] == '*')
                    {
                        waters.Enqueue(new int[] { i, j });
                        visited[i, j] = -1;
                    }

                    else if (row[j] == 'S')
                    {
                        hedgehog.Enqueue(new int[] { i, j });
                        visited[i, j] = 1;
                    }

                    else if (row[j] == 'D')
                    {
                        dest[0] = i;
                        dest[1] = j;
                    }
                }
            }

            int count = 1;
            while (visited[dest[0], dest[1]] == 0 && hedgehog.Count > 0)
            {
                waters = watersbfs(waters);
                hedgehog = hedgehogbfs(hedgehog, count);
                count++;
            }

            if (visited[dest[0], dest[1]] == 0)
                Console.WriteLine("KAKTUS");

            else
                Console.WriteLine(visited[dest[0], dest[1]]);
        }

        static Queue<int[]> watersbfs(Queue<int[]> q)
        {
            int[] dirY = { -1, 0, 1, 0 };
            int[] dirX = { 0, -1, 0, 1 };

            Queue<int[]> tmpq = new Queue<int[]>();

            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 (nextX < 0 || nextX >= C || nextY < 0 || nextY >= R)
                        continue;

                    if (forest[nextY, nextX] == 'X' || forest[nextY, nextX] == 'D')
                        continue;

                    if (visited[nextY, nextX] == -1)
                        continue;

                    visited[nextY, nextX] = -1;
                    tmpq.Enqueue(new int[] { nextY, nextX });
                }
            }

            return tmpq;
        }

        static Queue<int[]> hedgehogbfs(Queue<int[]> q, int count)
        {
            int[] dirY = { -1, 0, 1, 0 };
            int[] dirX = { 0, -1, 0, 1 };

            Queue<int[]> tmpq = new Queue<int[]>();

            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 (nextX < 0 || nextX >= C || nextY < 0 || nextY >= R)
                        continue;

                    if (forest[nextY, nextX] == 'X' || forest[nextY, nextX] == '*')
                        continue;

                    if (visited[nextY, nextX] == -1 || visited[nextY, nextX] > 0)
                        continue;

                    visited[nextY, nextX] = count;
                    tmpq.Enqueue(new int[] { nextY, nextX });
                }
            }

            return tmpq;
        }
    }
}