[백준/Python] DFS/BFS-1697번. 숨바꼭질

📌 문제링크:  https://www.acmicpc.net/problem/1697

 

✅ 문제유형: BFS/DFS 

 

✅ 풀이방법 

• 가장 빠른 시간을 출력해야 하니까 BFS를 선택했다. 
  • DFS/BFS 선택하는 전략: 2024.10.09 - [코딩테스트] - [알고리즘 전략] DFS/ BFS

[알고리즘 전략] DFS/ BFS

• <처음 코드> 시간초과 
  • 이유: time 값을 각 점에 방문 당시의 cnt값으로 queue에 같이 넣고 빼려 했더니, 자료구조 상 시간이 오래 걸리는 것 같다.
  • 📢 해결: 차라리 100,000개 배열인 visited를 선언하는 게 낫고, 여기에 각 점을 방문할 때의 시간을 저장해두는 게 효율적이다. 다른 문제 풀이에서도 graph 자체에 시간이나, 거쳐온 블록 수를 저장하듯이.

📌풀이코드 

N, K = map(int, input().split())

# 가장 빠른 시간을 출력해야 하니 bfs가 맞다
q = [] 
visited = [0 for _ in range(100000+1)]
answer = 0
def bfs(n):
    global answer
    q.append(n)
    while q:
        v = q.pop(0)
        if v == K: 
            answer = visited[v]
            break
            # stop 
        nextpos = [v-1, v+1, 2*v]
        for i in range(3):
            if 0<=nextpos[i]<=100000 and not visited[nextpos[i]]:
                q.append(nextpos[i])
                visited[nextpos[i]] = visited[v] + 1
bfs(N)
print(answer)

###############################################################
# 시간 초과 코드 
# def bfs(n, time):
#     global answer
#     q.append((n, time))
#     while q:
#         v, t = q.pop(0)
#         visited.append(v)
#         #print(f"v={v} t={t}")
#         if v == K: 
#             answer = t
#             break
#             # stop 
#         nextpos = [v-1, v+1, 2*v]
#         for i in range(3):
#             if 0<=nextpos[i]<=100000 and nextpos[i] not in visited:
#                 #print(f"APPEND v={nextpos[i]}, t={t+1}")
#                 q.append((nextpos[i], t+1))
# bfs(N)
# print(answer)