[백준] 13700 - 완전 범죄

1. 문제

13700번: 완전 범죄

2. 개요

도둑이 금은방을 털고 자신의 집으로 돌아가려 한다.

이 구역은 건물들이 모두 일자로 늘어서있다.

도둑은 한번에 앞, 뒤로 사전에 정해진 만큼만 이동할 수 있다.

건물들 중에는 경찰서가 섞여 있으며 도둑이 경찰서에 멈추게 된다면 잡히게 된다.

건물의 수, 금은방과 집의 위치, 앞, 뒤 이동 거리, 경찰서의 수와 위치가 주어졌을 때 도둑이 집까지 가기 위한 최소 이동 횟수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

BFS를 이용하여 답을 구한다.

visited배열을 이용하여 경찰서의 위치, 이동 횟수, 방문 여부를 한번에 체크한다.

현재위치에서 +F, -B가 다음 이동위치 next가 되며 next가 범위 내에 있고, 경찰서가 아니면서, 이미 방문한 곳이 아니라면 이동회수를 1씩 늘려주면서 방문체크를 한다.

큐가 다 비거나 목적지를 방문했다면 while문을 탈출한다.

목적지가 방문체크되었다면 목적지의 방문횟수를 출력하고 아니라면 BUG FOUND를 출력한다.

3-2. Python

import sys
from collections import deque

N, S, D, F, B, K = map(int, sys.stdin.readline().split())

visited = [-1 for i in range(N + 1)]

locs = list(map(int, sys.stdin.readline().split()))

for l in locs:
    visited[l] = -2

q = deque([S])
visited[S] = 0

while q and visited[D] == -1:
    nowX = q.popleft()

    for dirX in [F, -B]:
        nextX = nowX + dirX

        if nextX < 1 or nextX > N:
            continue

        if visited[nextX] != -1:
            continue

        visited[nextX] = visited[nowX] + 1
        q.append(nextX)

if visited[D] < 0:
    print("BUG FOUND")

else:
    print(visited[D])

3-3. C#

namespace boj_13700
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] info = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int N = info[0], S = info[1], D = info[2], F = info[3], B = info[4], K = info[5];

            int[] visited = new int[N + 1];
            int[] dirX = new int[] { F, -B };

            if (K > 0)
            {
                int[] locs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

                foreach (int l in locs)
                    visited[l] = -1;
            }
            
            Queue<int> q = new();
            q.Enqueue(S);
            visited[S] = 0;

            while (q.Count > 0 && visited[D] == 0)
            {
                int nowX = q.Dequeue();

                for (int i = 0; i < 2; i++)
                {
                    int nextX = nowX + dirX[i];

                    if (nextX < 1 || nextX > N)
                        continue;

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

                    visited[nextX] = visited[nowX] + 1;
                    q.Enqueue(nextX);
                }
            }

            if (visited[D] == 0)
                Console.WriteLine("BUG FOUND");

            else
                Console.WriteLine(visited[D]);
        }
    }
}