[백준] 12851 파이썬(python) : 숨바꼭질 2 - (visit수정)

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

12851번: 숨바꼭질 2

 

 

from collections import deque
import sys
n, k = map(int, sys.stdin.readline().split())
visit = [ [-1, 0] for _ in range(100001) ] #1

def bfs(n):
    q = deque([n])
    visit[n][0] = 0 #2
    visit[n][1] = 1 #3

    while q:
        x = q.popleft()
        for nx in (x-1, x+1, 2*x):
            if 0 <= nx <= 100000:
                if visit[nx][0] == -1: #4
                    visit[nx][0] = visit[x][0] + 1 #5
                    visit[nx][1] = visit[x][1]
                    q.append(nx)
                elif visit[nx][0] == visit[x][0] + 1: #6
                    visit[nx][1] += visit[x][1]
bfs(n)
print(visit[k][0])
print(visit[k][1])

 

#1 : 2차원 배열의 첫번째 요소는 시간, 두번째 요소는 방법 [ 최소시간, 방법 ]

#2, 3 : 처음시작하는 위치에선 시간 0, 방법 1로 설정

#4 : 처음방문이라면

#5 : 시간을 1초 추가

#6 : 새로운 위치를 처음방문은 아니지만 최단시간에 도착한것이라면

16 -> 17일때 16의 visit[16][0]는 3이고 18 -> 17일때 18의 visit[18][0]은 3이다. 그래서 18 -> 17일때는 16 -> 17에서 이미 방문했기에 visit[18][0] + 1 == visit[17][0]이 된다.

#7 : 다른곳을 거치고 오는것이기에 

 

예제에서 최소시간으로 가는 방법이 2가지가 나오는데 [ 5 -> 10 -> 9 -> 18 -> 17 ], [ 5 -> 4 -> 8 -> 16 -> 17 ] 이렇게 2가지가 있다.

 

#6같은 경우엔 bfs는 반드시 최소시간을 보장해 준다는 점을 기억해야 한다. 이미 한번 방문했다면 처음 방문할때 그 위치의 방문에선 최소시간으로 간것이기 때문에 두번째 부터 같은 장소에 방문하는것이라면 그 이전까지의 방문 순서는 차이가 있어도 그때도 최소시간일 것이다. 그래서 방법 1추가이다. 

 

비슷한 문제 (https://hgk5722.tistory.com/89)