[백준] 13700. 완전 범죄

문제 링크

[백준] 13700. 완전 범죄

풀이 과정

단순 BFS 탐색 문제입니다.

Queue<int[]> q = new LinkedList<>();
visit[S] = true;
q.add(new int[]{S, 0});

while (!q.isEmpty()) {
    int[] now = q.poll();

    if (now[0] == D) {
        answer = now[1];
        break;
    }

    int front = now[0] + F;
    if (front <= N && !police[front] && !visit[front]) {
        visit[front] = true;
        q.add(new int[]{front, now[1] + 1});
    }

    int back = now[0] - B;
    if (back >= 1 && !police[back] && !visit[back]) {
        visit[back] = true;
        q.add(new int[]{back, now[1] + 1});
    }
}

BFS 탐색 과정은 아래와 같습니다.

• 큐에서 뽑은 좌표가 목적지(D)이면, 버튼을 누른 최소 횟수를 answer 에 담고 루프를 탈출합니다.
• 전방과 후방 각각에 대해 갈 수 있는지 확인하고, 갈 수 있다면 방문 처리 후 큐에 넣습니다.
  • 다음의 조건을 만족해야 대도 X는 다음 위치로 이동할 수 있습니다.
    1. 전방(now[0] + F)과 후방(now[1] + B) 좌표가 배열 범위를 벗어나지 않으며,
    2. 해당 위치에 경찰서가 존재하지 않아야 하며,
    3. 방문한 적이 없어야 한다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int S = sc.nextInt();
        int D = sc.nextInt();
        int F = sc.nextInt();
        int B = sc.nextInt();
        int K = sc.nextInt();
        boolean[] police = new boolean[N + 1];
        boolean[] visit = new boolean[N + 1];
        int answer = 0;

        for (int i = 0; i < K; i++) police[sc.nextInt()] = true;

        Queue<int[]> q = new LinkedList<>();
        visit[S] = true;
        q.add(new int[]{S, 0});

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[0] == D) {
                answer = now[1];
                break;
            }

            int front = now[0] + F;
            if (front <= N && !police[front] && !visit[front]) {
                visit[front] = true;
                q.add(new int[]{front, now[1] + 1});
            }

            int back = now[0] - B;
            if (back >= 1 && !police[back] && !visit[back]) {
                visit[back] = true;
                q.add(new int[]{back, now[1] + 1});
            }
        }

        System.out.println(answer == 0 ? "BUG FOUND" : answer);
    }
}