[알고리즘] 백준 1697 숨바꼭질 (파이썬 풀이)

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

1697번: 숨바꼭질

해결코드

from collections import deque

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()
        if x==k:
            print(dist[x])
            break
        for j in (x-1,x+1,x*2):
            if(0<=j<=MAX and not dist[j]):
                dist[j] = dist[x]+1
                q.append(j)
                
n,k = map(int, input().split())
MAX = 100000
dist = [0]*(MAX+1)
bfs()

문제풀이

bfs를 이용하여 해결할 수 있는 문제이다.

큐를 이용해야 하는데 파이썬에서 큐를 이용할 때는 deque을 사용하는게

시간초과에 안걸릴 수 있다.

 

코드를 보자

 

n,k = map(int, input().split())
MAX = 100000
dist = [0]*(MAX+1)

각자의 위치 n,k를 입력받아주고

문제에서 좌표의 최대값이 100000이라고 주어졌으니 MAX값을 100000으로 초기화한다.

dist라는 변수에는 MAX+1개의 0을 가진 리스트를 저장한다.

 

def bfs():
    q = deque()
    q.append(n)

bfs함수를 보면

q라는 덱하나를 생성해주고

n값을 추가해준다.

    while q:
        x = q.popleft()
        if x==k:
            print(dist[x])
            break

q의 원소가 있는동안 while문을 실행한다

q의 원소를 왼쪽에서 제거하고 x값에 저장한다.

만약 x와 k가 같다면(동생의 위치와 같다면)

dist[x]를 출력하고 멈춘다.

        for j in (x-1,x+1,x*2):
            if(0<=j<=MAX and not dist[j]):
                dist[j] = dist[x]+1
                q.append(j)

x-1,x+1,x*2의 값으로 for문을 실행시킨다(예를 들어 x=5이면 j=4,6,10)

만약 j가 0과 MAX값 사이의 값이고 dist[j]와 같지않다면

dist[j]는 dist[x]+1이다.(처음 dist[x]는 무조건 0이다) ex) dist[4,6,10]=0+1

그리고 j값을 q에 추가해준다.