*문제 출처는 백준에 있습니다.
문제 제목: 숨바꼭질 2 / 12851번 (골드 4단계)
문제 사이트: https://www.acmicpc.net/problem/12851
문제 설명

나의 풀이
from collections import deque
def bfs(n, k):
answer = 0 # 방법의 수
times = [100001] * 100001 # 각 위치에 도달하는 최소 시간, 최대 시간으로 초기화
dq = deque([(n, 0)]) # 큐에 (위치, 시간) 형태로 삽입
times[n] = 0 # 수빈이의 시작 위치 시간은 0초
ways = [0] * 100001 # 각 위치에 도달하는 방법의 수
ways[n] = 1 # 시작 위치는 방법의 수가 1
while dq:
value, seconds = dq.popleft() # 위치와 현재 시간을 가져옴
if value == k: # 동생을 찾았다면
if seconds < times[k]:
times[k] = seconds
answer = ways[k] # 방법의 수 갱신
elif seconds == times[k]:
answer += ways[k] # 같은 시간에 여러 방법이 있을 수 있음
# 이동 가능한 세 가지 경우 (X-1, X+1, 2*X)
for next_pos in [value - 1, value + 1, value * 2]:
if 0 <= next_pos <= 100000: # 유효한 범위 내에서만 이동
if times[next_pos] == 100001: # 아직 방문하지 않은 곳
times[next_pos] = seconds + 1
ways[next_pos] = ways[value] # 처음 도달하는 경우
dq.append((next_pos, seconds + 1))
elif times[next_pos] == seconds + 1: # 최소 시간으로 도달한 경우
ways[next_pos] += ways[value] # 방법의 수 누적
print(times[k]) # 동생의 위치에 도달하는 최소 시간
print(answer) # 최소 시간으로 도달하는 방법의 수
def main():
n, k = map(int, input().split()) # n: 수빈이 위치, k: 동생 위치
bfs(n, k)
main()

※ 알아야 할 것
times = [100001] * 100001
BFS에서 각 위치를 한 번만 방문하여 탐색을 진행해야 합니다. 만약 방문 처리를 하지 않으면, 같은 위치를 여러 번 방문하면서 동일한 위치를 다시 탐색하게 됩니다. 이로 인해 이미 방문한 위치에 대해 다시 탐색을 진행하면 불필요한 계산이 발생하고, 시간 복잡도가 증가합니다. 방문을 기록하지 않으면 같은 위치를 큐에 여러 번 넣을 수 있으며, 큐의 크기가 불필요하게 커지고 탐색이 비효율적으로 이루어집니다.
'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 특정 거리의 도시 찾기 / 18352번 / Python (0) | 2025.03.26 |
|---|---|
| 백준 / 구간 합 구하기 5 / 11660번 / Python (0) | 2025.03.26 |
| 백준 / 캠프가는 영식 / 1590번 / Python (0) | 2025.03.23 |
| 백준 / 로봇 청소기 / 14503번 / Python (2) | 2025.03.21 |
| 백준 / 다리 만들기 / 2146번 / Python (0) | 2025.03.20 |