[백준] 1657. 숨바꼭질

문제 출처

www.acmicpc.net/problem/1697

문제 설명

1차원 좌표계에서 경로를 탐색하는 문제다.

문제 풀이

bfs로 풀었다.

현재 있는 점에서 갈 수 있는 모든 방향을 큐에 넣는다.

큐에 목적지가 있다면 결과를 출력하고 종료한다.

코드

코드 해설

public static void main(String[] args) {
    readInput();
    int answer = bfs();
    System.out.println(answer);
}

메인은 항상 직관적으로 구성한다.

1. 입력을 받는다.

2. 연산한다.

3. 결과를 출력한다.

public static int move(int x, int method) {
    switch(method) {
        case 0:
            return x - 1;
        case 1:
            return x + 1;
        case 2:
            return x * 2;
    }
    return -1;
}

탐색하는 코드 내부에서 쓸 메서드이다.

수빈이는 3가지 방법으로 움직일 수 있고 이 코드엔 현재 위치에 3가지 방법 중 어떤걸 할 지를 전달하면

움직인 결과를 돌려준다.

public static boolean inRange(int x) {
    return 0 <= x && x < 200000;
}

탐색하는 코드 내부에서 쓸 메서드이다.

수빈이는 x = 100,000 에 서서 2배로 뛰는 경우까지 생각했다.

그 이상은 절대 갈 필요가 없다.

200,000이 아닌 더 짧게 잡아줘도 되지만 크게 개선될 여지가 없어서 길게 고민하지 않았다.

while (!queue.isEmpty()) {
    Coord current = queue.poll();
    if (current.x == k) {
        return current.time;
    }
    for (int method = 0; method < 3; method++) {
        Coord next = new Coord(move(current.x, method), current.time + 1);
        if (inRange(next.x) && !visited[next.x]) {
            queue.offer(next);
            visited[next.x] = true;
        }
    }
}

큐를 하나 꺼내서 목적지에 도착이라면 결과를 돌려준다.

그렇지 않다면 갈 수 있는 모든 방향을 큐에 넣는다.

이 때 방문체크를 하지않는다면 빙글빙글도는 무한 루프에 빠지게 된다.

방문체크를 통해 한번 갔던 길(한번 연산한 좌표)은 다시 가지 않도록 확인 후에 큐에 넣자.

이론상 !queue.isEmpty()에 의해 종료될 일은 없고 항상 return current.time; 의 결과를 돌려준다.