[BOJ] 1697번: 숨바꼭질

 

 

문제 링크

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

 

 

 

TIL

• 가장 빠른 >> BFS !!!!!!!!!!!!
  • 최단 시간, 최단 거리를 묻는 문제는 묻지도 따지지도 않고 BFS 사용하기

 

[메모리 초과 - visited set() 사용]

# bfs >> 가장 빠른 시간
from collections import deque

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

queue = deque()
queue.append((n, 0))  # current_location, time
visited = set()
visited.add(n)

while queue:
    current, time = queue.popleft()
    visited.add(current)

    if current == k:
        print(time)
        break
    
    for i in (current+1, current-1, current*2): # walk_forward, walk_backward, teleport
        if i not in visited:
            queue.append((i, time+1))

• 메모리 초과 원인 예상
  • set() 에 너무 많은 값이 저장됨
  • 만약에 list로 저장하면 max 값이 정해져있기에 충분히 핸들링 가능
• BFS도 visited check 필수 !!!!!
  • 갔던 곳을 굳이 또 방문하지 않아야 함 > 이래야지 시간 초과도 안남
• set()이나 dict()를 사용하는 거보단 list가 메모리나 시간 효율이 좋음 !!
  • 특별한 일 아니면 list 사용하기 > 특히 이런 범위가 큰 문제에 대해선 시간 복잡도 생각해야함
  • 만약에 범위가 작다면 set()도 가능
•  for i in (current+1, current-1, current*2): 이런 형태의 코드도 생각하기 

 

 

Code

# bfs >> 가장 빠른 시간
from collections import deque

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

queue = deque()
queue.append((n, 0))  # current_location, time
visited = [False for _ in range(100002)]
visited[n]=True

while queue:
    current, time = queue.popleft()
    visited[current] = True

    if current == k:
        print(time)
        break
    
    for i in (current+1, current-1, current*2): # walk_forward, walk_backward, teleport
        if 0<=i<100001 and not visited[i]:
            queue.append((i, time+1))

 

• index 범위 조심 !! 
  • 문제에서 0부터 100000까지 이동가능하니 100002까지 만들어야하며, 범위 체크도 100000가 포함되어야 한다