[백준] 1697 - 숨바꼭질 (Python)

5 Aug 2021

[백준] 1697 - 숨바꼭질

문제 출처: https://www.acmicpc.net/problem/1697
알고리즘:
- 그래프이론
- 그래프탐색
- 너비 우선 탐색

풀이 - BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import deque

N,K=map(int,input().split())
visited=[0]*100001
queue=deque()

def bfs(x):
    queue.append((x,0))
    visited[x]=1
    while queue:
        x=queue[0][0]
        cnt=queue[0][1]
        queue.popleft()
        if x==K:
            print(cnt)
            break

        for nx in (x-1,x+1,x*2):
            if nx>=0 and nx<=100000 and visited[nx]==0:
                queue.append((nx,cnt+1))
                visited[nx]=1

bfs(N)

✍ 처음에 문제를 풀었을 때 메모리 초과 문제가 발생했었는데

방문 여부를 검사하는 visited list를 통해 중복값 처리 방지
다음의 x값의 범위를 0 ≤ nx ≤ 100000으로 설정

위와 같은 방법을 통해 문제를 해결할 수 있었다.

algorithms