백준 1697번 : 숨바꼭질

게시 2023/11/14

By Jeremiah Lee 10 분 : 읽는 시간

이번 문제는 X와 Y가 있을 때 X가 Y에 도달하기 까지 가장 짧은 시간을 구하는 문제이다.

특히 이 X는 초 단위로 -1 또는 +1 만큼 이동할 수도 있고 *2 만큼 이동도 가능하다.

가장 먼저 이 문제는 1차원 배열에서 이동하는 것으로 표현한다.
또한, 나는 BFS 탐색을 별개의 함수에 정의할 것이므로 공통적으로 필요한 변수를 멤버 변수로 선언했다.

  
public class Main {
    static int[] arr;
    static boolean[] visited;
    static int max = 100001;
}

첫 번째로 필요한 것은 이동 가능한 위치를 지정하는 정수형 1차원 배열이다.

다음으로는 탐색을 위해 사용할 방문 여부 체크 배열, 그 다음으로는 문제에서 지정해준대로 탐색 최대치를 정해준다.

이 탐색 최대치 같은 경우는 각각 전체 루트인 arr, 해당 루트를 방문했는지 여부를 체크할 visited 배열의 크기를 지정하는데에 사용할 수 있다.

사용할 멤버 변수를 정했다면 다음으로는 입력 값을 가공할 수 있어야 한다.

  
public static void main(String[] args) throws java.io.IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    arr = new int[max];
    visited = new boolean[max];

    bfs(n, k);

    System.out.println(arr[k]);
}

메인 함수에서 각 입력 값들을 초기화한다.

시작 점인 n과 k를 받아오고 기존에 지정한 최대값을 바탕으로 arr과 visited 배열의 크기를 설정한다.

이후 bfs 탐색을 실행한다.

이번 문제는 최단거리 탐색 문제이며, 주어진 조건이 다양한 만큼 이 탐색 알고리즘이 가장 중요하다.

  
public static void bfs(int start, int end) {
    visited[start] = true;
    arr[start] = 0;

    Queue<Integer> q = new LinkedList<>();
    q.offer(start);

    while (!q.isEmpty()) {
        int cur = q.poll();
        
        if (cur == end) {
            break;
        }

        if (cur - 1 >= 0 && !visited[cur - 1]) {
            q.offer(cur - 1);
            visited[cur - 1] = true;
            arr[cur - 1] = arr[cur] + 1;
        }
        if (cur + 1 < max && !visited[cur + 1]) {
            q.offer(cur + 1);
            visited[cur + 1] = true;
                arr[cur + 1] = arr[cur] + 1;
        }
        if (cur * 2 < max && !visited[cur * 2]) {
            q.offer(cur * 2);
            visited[cur * 2] = true;
            arr[cur * 2] = arr[cur] + 1;
        }
    }
}

우선 함수를 정의할 때, 다음 칸으로 이동하는 경우에 +1씩 초 단위를 합치며 이동하기 때문에 별도의 리턴 값은 필요하지 않다.

다시 말해, 전체 루트인 arr에 상태값이 저장되는 방식으로 탐색을 하기 때문에 최종적으로는 arr에 도달한 인덱스의 값만 출력하면 된다.

다음으로 함수의 시작은 기존 탐색 알고리즘과 동일하다.

현재 위치의 방문 여부를 true로 변경하고, 현재 위치가 시작 지점이기 때문에 arr의 시작 지점 인덱스의 요소는 0초 부터 시작한다.

여기서 arr에는 초 단위가 기록될 것이기 때문이다.

다음으로는 BFS 탐색을 위해 큐를 선언하고 시작 위치를 삽입한다.

이제 while 문을 실행시켜 bfs 탐색을 시작할 것이다.

단, 이 문제에서는 이동 방식이 3개로 나뉘기 때문에 탐색 시 조건이 3개인 점을 주의해야한다.

이동 조건

  
if (cur - 1 >= 0 && !visited[cur - 1]) {
    q.offer(cur - 1);
    visited[cur - 1] = true;
    arr[cur - 1] = arr[cur] + 1;
}

이 조건은 X가 -1 만큼 이동했을 경우이다.

조건을 살펴보면 cur : 현재 위치에서 -1 만큼 이동한 위치가 유효 범위인 0 이상이고, 아직 방문하지 않은 노드인지 확인한다.

이 조건에 맞으면

해당 위치를 큐에 추가
해당 위치 방문 여부 true
해당 위치 = 이전 위치 + 1 로 1초 추가

를 진행한다.

나머지 두 개의 조건도 동일한 방식으로 작동하며 이 로직들이 반복되는 경우에 arr의 이동한 인덱스 위치에 1초 씩 더 해 나간다.

반복 후 이 로직이 종료되면 arr[k] 자리에는 최종 시간이 기록된다.

마지막으로 종료 조건인데,
처음에는 이 로직을 넣지 않았었다.

그런데 이 풀이 자체가 100001까지의 모든 경우의 수를 구한 다음 k 번째를 리턴하도록 되어 있어서 테스트 케이스가 시작 지점과 가까울수록 효율이 떨어지는 것 같아서 넣었다.

  
while (!q.isEmpty()) {
    int cur = q.poll();
        
    if (cur == end) {
        break;
    }

이 종료 조건은 cur가 end에 도달하면 멈추게끔 설정했는데,
막상 문제의 테스트 케이스들은 거리가 먼 것인지 유의미한 시간 단축이 되지 않아서 직접 값을 대입해보고 시간을 체크해보았다.

그랬더니 종료 지점이 가까울 수록 거의 100배가 넘는 시간 효율 차이를 보여 그대로 둔 것이다.

전체 소스코드는 다음과 같다.

  
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    static boolean[] visited;
    static int max = 100001;

    public static void main(String[] args) throws java.io.IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        arr = new int[max];
        visited = new boolean[max];

        bfs(n, k);

        System.out.println(arr[k]);
    }

    public static void bfs(int start, int end) {
        visited[start] = true;
        arr[start] = 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

        while (!q.isEmpty()) {
            int cur = q.poll();

            if (cur == end) {
                break;
            }

            if (cur - 1 >= 0 && !visited[cur - 1]) {
                q.offer(cur - 1);
                visited[cur - 1] = true;
                arr[cur - 1] = arr[cur] + 1;
            }
            if (cur + 1 < max && !visited[cur + 1]) {
                q.offer(cur + 1);
                visited[cur + 1] = true;
                arr[cur + 1] = arr[cur] + 1;
            }
            if (cur * 2 < max && !visited[cur * 2]) {
                q.offer(cur * 2);
                visited[cur * 2] = true;
                arr[cur * 2] = arr[cur] + 1;
            }
        }
    }
}

이 쯤 오니 오히려 1차원 배열 문제를 풀어서인지 엄청 헷갈렸다.

특히 이동에 대한 조건이 여러 개일 경우는 처음 접해봐서 헤맸다.

그리고… 스도코드를 좀 작성하면서 풀어야 되는데 의사코드 작성이 왜이리 불편한건지 모르겠다.

의사코드 작성을 해서 먼저 틀을 짜고 풀어내는 게 훨씬 도움이 될텐데, 자꾸 암산하고서 풀려고 해서 막막하게 느끼는 경향이 있는거 같다.

습관이 되어버린거 같은데 조금 씩 고쳐보자고 생각 중이다.

알고리즘, 백준

알고리즘 백준

이동 조건

인기 태그