[BOJ][BFS] 1697. 숨바꼭질 (java / python)

✏️ 문제

문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

🔢 알고리즘

 

#BFS  #그래프

 

 

🤯 풀이 방법

BFS를 이용해서

다음 초에 갈 수 있는 세 위치를 저장하고,

다음 단계에서는 이전에 저장해 둔 각각의 위치에서 또 이동할 수 있는 위치를 저장한다.

HashMap을 사용했는데 BFS인걸 알면서 왜 큐를 안 썼지? 정신챙기자

 

👾 구현 코드 (자바)

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();   // 수빈이의 위치
        int K = sc.nextInt();   // 동생의 위치

        int ans = 0;

        // 단계(시간)을 저장하는 BFS

        // N - 1, N + 1, N * 2 를 단계와 함께 저장
        int[] visited = new int[100001];
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        map.put(0, new ArrayList<>(List.of(N)));   // 시작할 수빈이의 위치 0초로 시작
        visited[N] = 1;
        if (N == K) {
            System.out.println(0);
            return;
        }

        while (true) {
            List<Integer> pre = map.get(ans);   // 이전에 저장해둔 위치 배열을 찾는다
            List<Integer> move = new ArrayList<>();
            ans++;
            for (int p : pre) {
                int[] cur = new int[]{p + 1, p - 1, p * 2}; // 다음에 갈 수 있는 경우의 수
                for (int c : cur) {
                    if (c < 0 || c > 100000) {  // 가능 범위 체크
                        continue;
                    }
                    if (c == K) {   // 정답에 도달한 경우
                        System.out.println(ans);
                        return;
                    } else if (visited[c] == 0) {   // 아직 방문하지 않은 곳이면
                        move.add(c);    // 다음 초에 갈 수 있는 후보로 포함
                        visited[c] = 1;
                    }
                }
            }
            map.put(ans, move);

        }


    }
}

 

 

🤖 GPT의 개선 제안

 

1. HashMap 대신 큐 사용 

HashMap<Integer, List<Integer>> map을 사용하여 단계별로 저장하는 방식은 다소 비효율적입니다. BFS에서는 일반적으로 Queue를 사용하여 탐색 대상을 관리합니다. 이는 메모리 사용량을 줄이고 구현을 단순화합니다.

 

Queue<Integer> queue = new LinkedList<>();
queue.add(N);
visited[N] = 1;

while (!queue.isEmpty()) {
    int size = queue.size(); // 현재 단계에서 처리할 노드 수
    for (int i = 0; i < size; i++) {
        int p = queue.poll();

        int[] cur = new int[]{p + 1, p - 1, p * 2}; // 다음 가능한 위치
        for (int c : cur) {
            if (c < 0 || c > 100000) continue; // 범위를 벗어나는 경우 스킵
            if (c == K) { // 동생의 위치에 도달하면 정답 출력
                System.out.println(ans + 1);
                return;
            }
            if (visited[c] == 0) { // 방문하지 않은 경우만 처리
                queue.add(c);
                visited[c] = 1;
            }
        }
    }
    ans++; // 현재 단계의 처리가 끝나면 시간 증가
}

 

2. visited 배열 초기화 및 상태 확인 개선

현재 visited 배열에 0 또는 1로만 방문 상태를 관리하고 있지만, 시간을 기록하도록 바꿀 수도 있습니다. 이렇게 하면 메모리를 재사용하고, 방문 여부와 시간을 동시에 관리할 수 있습니다.

int[] visited = new int[100001];
Arrays.fill(visited, -1); // 초기화: -1은 방문하지 않은 상태

queue.add(N);
visited[N] = 0; // 시작 위치의 시간은 0

while (!queue.isEmpty()) {
    int p = queue.poll();

    if (p == K) { // 동생의 위치에 도달
        System.out.println(visited[p]);
        return;
    }

    int[] cur = new int[]{p + 1, p - 1, p * 2};
    for (int c : cur) {
        if (c < 0 || c > 100000 || visited[c] != -1) continue; // 범위 초과 또는 이미 방문
        visited[c] = visited[p] + 1; // 이전 시간 +1
        queue.add(c);
    }
}

 

 

 

---

+)

👾 구현 코드 (파이썬)

from collections import deque

def bfs():
    while q:
        a = q.popleft()

        if a == K:
            print(M[a])
            break

        else:
            for i in (a - 1, a + 1, a * 2):
                if 0 <= i <= m and M[i] == 0:
                    M[i] = M[a] + 1
                    q.append(i)

N, K = map(int, input().split())    # N: 수빈이의 위치, K: 동생의 위치
m = 100000
M = [0] * (m + 1)


q = deque()
q.append(N)

bfs()