[bfs/백준] 12851번 : 숨바꼭질2

- 문제 : https://www.acmicpc.net/problem/12851

 

문제 이해

- 이전에 풀었던 숨바꼭질 문제에서 최소 시간으로 도착하는 경우의 수를 출력하는 것이 추가된 문제다. 

- 경우의 수를 구하는 게 살짝 어려웠다. 

 

풀이 로직

- 이차 행렬인 visit를 이용해서 방문여부와 경우의 수를 기록하면서 전체 bfs를 진행한다.

- 다음 노드가 처음 방문하는 노드인 경우는 경우의 수가 동일하고, 다음 노드가 이전에 방문한 노드인 경우에는 경우의 수를 합친다. 

- bfs가 끝나고 난뒤 도착점이 k에서의 최소시간과 경우의 수를 출력한다. 

 

정답 풀이 

골드 문제중에 2차 행렬을 이렇게 설정하는게 있는데 이 부분이 부족해서 익숙하지 않은 것 같다. 여러번 연습이 필요한 것 같다. 

n, k = map(int, input().split())

number = 10 ** 5
visit = [[-1, 0] for _ in range(number + 1)] # [도착까지 걸리는 시간, 경우의 수]

queue = [n]
visit[n][0] = 0 
visit[n][1] = 1
while queue:
    x = queue.pop(0)
        
    for nx in [x - 1, x + 1, 2 * x]:
        if 0 <= nx <= number:
            if visit[nx][0] == -1: # 처음 방문하는 지점이면
                visit[nx][0] = visit[x][0] + 1 
                visit[nx][1] = visit[x][1] # 경우의 수는 동일함
                queue.append(nx)
            elif visit[nx][0] == visit[x][0] + 1: # 다음 노드가 이전에 방문한 노드인 경우 + 최단 시간으로 도착한 경우
                visit[nx][1] += visit[x][1] # 경우의 수 합치기
            
print(visit[k][0])
print(visit[k][1])

 

참고 블로그 : [백준] 12851번: 숨바꼭질4