백준 13700번 - 완전 범죄 [JAVA]

문제 : 링크

 

이 문제는 시작점에서 도착점까지 제시된 방법에 따라 이동했을 때 최소 이동 횟수를 찾는 문제입니다.

 

 

풀이

각각의 입력 값을 받고 bfs를 통해 현재 위치에 대해서 이동가능한지 조건에 따라 확인 후 이동 가능하면 노드에 위치와 이동 횟수를 입력 받아서 다시 큐에 그 노드를 넣어서 bfs를 통해 탐색할 수 있도록 한다.

노드를 큐에서 뺄 때 도착점과 같다면 answer변수에서 노드에 담긴 count를 받아서 출력한다.
큐에 있는 데이터가 모두 빠졌는데 도착하지 못했다면 answer는 0일 것이고 도착할 수 없다는 뜻으로 BUG FOUND를 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * https://www.acmicpc.net/problem/13700
 * silver1
 * 완전범죄
 */

class Node {
    // 위치와 이동횟수를 담을 변수
    int index;
    int count;

    public Node(int index, int count) {
        this.index = index;
        this.count = count;
    }

    public int getIndex() {
        return index;
    }

    public int getCount() {
        return count;
    }
}

public class BOJ_13700_1 {
    static Set<Integer> office = new HashSet<>();
    static int N;
    static int S;
    static int D;
    static int F;
    static int B;
    static int K;
    static boolean[] visited;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        // 마포구 건물의 개수
        N = Integer.parseInt(stringTokenizer.nextToken());

        // 털린 금은방(시작 위치)
        S = Integer.parseInt(stringTokenizer.nextToken());

        // 대도 x의 집(목표 위치)
        D = Integer.parseInt(stringTokenizer.nextToken());

        // 앞으로 한번에 달릴 수 있는 건물 수
        F = Integer.parseInt(stringTokenizer.nextToken());

        // 뒤로 한번에 달릴 수 있는 건물 수
        B = Integer.parseInt(stringTokenizer.nextToken());

        // 경찰서의 개수
        K = Integer.parseInt(stringTokenizer.nextToken());

        visited = new boolean[N + 1];

        // k가 0보다 크면 경찰서에 대한 정보를 담음
        if (K > 0) {
            stringTokenizer = new StringTokenizer(br.readLine());
            while (stringTokenizer.hasMoreTokens()) {
                office.add(Integer.valueOf(stringTokenizer.nextToken()));
            }
        }

        bfs(new Node(S, 0));

    }

    static void bfs(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        // 정답을 담을 변수
        int answer = 0;

        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            if (currentNode.getIndex() == D) {
                answer = currentNode.getCount();
                break;
            }
            // 현위치
            int x = currentNode.getIndex();

            visited[x] = true;

            int frontMoved = x + F;
            int backMoved = x - B;

            /*System.out.println("x = " + x);
            System.out.println("frontMoved = " + frontMoved);
            System.out.println("backMoved = " + backMoved);
            System.out.println("visited[frontMoved] = " + visited[frontMoved]);
            System.out.println("visited[backMoved] = " + visited[backMoved]);*/


            // 이동했을 때 경찰서인지 검사
            boolean frontMoveIsPolice = office.contains(frontMoved);
            boolean backMoveIsPolice = office.contains(backMoved);

            // frontMoveIsPolice 값
            // true ==  앞으로 갔을 때 경찰서가 있음, false == 앞으로 갔을 때 경찰서가 없음
            if (!frontMoveIsPolice && frontMoved <= N && !visited[frontMoved]) {
                visited[frontMoved] = true;
                queue.add(new Node(frontMoved, currentNode.getCount() + 1));
            }
			
            if (!backMoveIsPolice && backMoved >= 1 && !visited[backMoved]) {
                visited[backMoved] = true;
                queue.add(new Node(backMoved, currentNode.getCount() + 1));
            }
        }

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