[알고리즘/BFS & DFS] 12851번 : 숨바꼭질 2 - python

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

12851번: 숨바꼭질 2

 

---

• 문제
• 소요시간: 45분(50%) 통과

---

• 설계하기(접근방법) 

1. 입력받기

숫자를 입력받는다

 

2. 구현하기

이 문제의 어려웠던 점은 최소시간을 구하는 것이 아닌

최소 시간의 방법 수를 구하는 것이었다

즉

1 -> 4로 가는 경우

1+1

2 * 2

를 하거나

1 * 2

2* 2

두 가지 방법이 있는데 이 두 가지 경우를 어떻게 체크하냐 였다.

 

que에 append를 할 때, 

vistied[nx]가 0일 때만이 아닌 -> 처음 최단경로

visited[nx] 가 visited[x] + 1일 때 -> 도착지가 target일 때 또 다른 최단경로 케이스인지 아닌지

즉  중복되는 경우를 cnt하면 된다

 

3. 출력하기

cnt를 출력한다

 

---

• 코드(출력)

import sys
from collections import deque
start, target= map(int, sys.stdin.readline().split())
queue = deque()
queue.append(start)
visited = [0]*100001 # 최대 크기
cnt, result = 0,0
while queue:
    x =  queue.popleft()
    temp = visited[x]
    if x == target: # 둘이 만났을 때
        result = temp # 결과
        cnt += 1 # 방문 횟수 +1
        continue
    
    for i in [x-1, x+1, x*2]:
        if 0 <= i < 100001:
            if visited[i] == 0:
                visited[i] = visited[x] + 1
                queue.append(i)
            elif visited[i]== visited[x] +1: #범위 안에있고 방문하지 않았거나, 다음 방문이 이전 방문+1이면
                queue.append(i) 
print(result)
print(cnt)

---

• 얻어갈 부분

1. 보통 print를 통해 알고리즘의 시간 내에 풀 수 있는지 없는지 확인했었는데, I/O 문제때문에 print 함수가 느리다는 것을 알게되었다. 즉 print로 출력시 무한루프가 도는 것 같아 코드를 수정했는데, 알고보니 print 자체가 속도가 걸려서 계산과는 큰 상관 없었다. 다음에는 리스트에 넣고 한꺼번에 출력하는 방식으로 무한루프를 확인하자.