99클럽 코테 스터디 7일차 TIL - BFS

문제 💁🏻‍♂️

문제 링크 - 백준 1697 숨바꼭질

해결 과정

이 문제는 전형적인 BFS 문제이다. 문제를 간단하게 요약해보면 수빈이가 동생을 찾는 가장 빠른 시간을 구하는 것이다. 즉, 최단 거리를 구하는 문제라고 해석할 수 있다.

사고 과정 ❗️

파이썬으로는 BFS 문제는 from collections import deque 를 사용해서 풀었는데, 자바에도 이와 비슷한 ArrayDeque<> Collection 프레임워크가 존재하여 이를 사용하여 풀이하였다. BFS 과정은 다음과 같다.

1. 수빈이의 위치와 초기화 거리값으로 초기화한 Point 객체를 ArrayDeque에 넣는다.
2. Queue 특성을 활용해서 너비우선탐색인 BFS를 실행한다. 즉, 현재 객체에서 갈 수 있는 가능한 모든 다음 위치를 Queue에 넣는다.
   2-1. 범위를 신경써야 한다.
3. 큐에서 뽑고, 다음으로 가능한 위치 객체를 큐에 다시 넣는 과정을 반복하다가 동생의 위치와 일치하는 위치 객체가 나온다면 즉시 해당 거리값을 return 한다.

아마 BFS 알고리즘을 활용하는 가장 기본적인 문제이기 때문에 별다른 추가 조건없이 문제를 해결할 수 있었다! 추가적으로 그냥 간단한 입력과 출력이기 때문에 Scanner를 사용했다!

코드

정답 코드

import java.io.*;
import java.util.*;

public class Main {

    static class Point {
        int idx, cnt;

        Point(int idx, int cnt) {
            this.idx = idx;
            this.cnt = cnt;
        }
    }

    static Scanner sc = new Scanner(System.in);
    static int N, K, MAX = 100_000;

    public static void main(String[] args) {

        N = sc.nextInt();
        K = sc.nextInt();

        int cnt = search();
        System.out.println(cnt);
    }

    private static int search() {

        ArrayDeque<Point> dq = new ArrayDeque<>();
        boolean[] visited = new boolean[MAX + 1];
        visited[N] = true; // 시작 지점 방문 처리
        dq.offer(new Point(N, 0));

        while (!dq.isEmpty()) {

            Point curr = dq.poll();

            if (curr.idx == K)
                return curr.cnt;

            for (int nxt : new int[]{curr.idx - 1, curr.idx + 1, curr.idx * 2}) {
                // 방문하지 않은 경우
                if (inRange(nxt) && !visited[nxt]) {
                    visited[nxt] = true; // 방문 처리
                    dq.offer(new Point(nxt, curr.cnt + 1));
                }
            }
        }

        return -1;
    }

    private static boolean inRange(int x) {
        return 0 <= x && x <= MAX;
    }

}

Reference

• 내 머릿 속