[Python/Java] 백준 1697 - 숨바꼭질 [BFS]

문제

https://www.acmicpc.net/problem/1697

 

해설

최단 경로를 탐색하는 문제이므로 BFS를 사용하였다. 

 

Python

queue에서 pop하는 과정은 deque 자료구조를 활용하여 시간초과에 관한 문제를 개선하였다.

 

이후 set을 이용하여 visited를 저장하였지만, 메모리 초과가 발생하였다. 이 부분을 list를 이용하여 최대 사이즈를 지정하여 메모리 초과를 해결할 수 있었다.

 

from sys import stdin
from collections import deque


MAX = 100001


def bfs(start: int, end: int):
    visited = [False] * MAX
    visited[start] = True
    queue = deque([(start, 0)])

    while queue:
        current, steps = queue.popleft()

        if current == end:
            return steps

        for neighbor in [current - 1, current + 1, current * 2]:
            if 0 <= neighbor < MAX and not visited[neighbor]:
                visited[neighbor] = True
                queue.append((neighbor, steps + 1))


n, k = map(int, stdin.readline().split(" "))
print(bfs(n, k))

 

Java

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


public class Main {
    static int MAX = 1000001;

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

        String[] condition = br.readLine().split(" ");
        int n = Integer.parseInt(condition[0]);
        int k = Integer.parseInt(condition[1]);
        
        System.out.println(bfs(n, k));
    }

    public static int bfs(int start, int end){
        int[] visited = new int[MAX];
        visited[start] = 1;

        Deque<List<Integer>> queue = new ArrayDeque<>();
        queue.add(List.of(start, 0));

        while(!queue.isEmpty()){
            List<Integer> item = queue.poll();
            int current = item.get(0);
            int steps = item.get(1);

            if(current==end){ return steps; }

            for(int neighbor : List.of(current-1, current+1, current*2)){
                if(0<=neighbor && neighbor<MAX && visited[neighbor]!=1){
                    visited[neighbor] = 1;
                    queue.add(List.of(neighbor, steps+1));
                }
            }
        }
        return 0;
    } 
}