[백준 13549번] 숨바꼭질 3 - python

문제 링크

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

풀이

- bfs 를 사용해서 풀었는데 틀렸다고 떴다.

- bfs를 사용하기 위해서는 모든 간선의 가중치가 동일해야한다는 전제 조건이 필요하기 때문이라고 한다. 

본 문제의 경우 x*2로 순간이동하는 경우는 가중치가 0이기 때문에 일반적인 bfs를 사용하면 안되고, 

가중치가 0인 간선에 연결된 정점의 경우 큐의 맨 뒤가 아닌 맨 앞에 넣어줘야 한다. 

따라서 단순한 bfs를 사용한 아래 코드는 틀린 코드이다.

# 틀린 코드 
from collections import deque 

def bfs(n):
  visited[n] = True

  q= deque()
  q.append((n,0))

  while q:
    x, cnt = q.popleft()

    if x == k:
      return cnt
      
    if 0 <= x-1 <= 100000 and not visited[x-1]:
      visited[x-1] = True
      q.append((x-1,cnt+1))
    if 0 <= x+1 <= 100000 and not visited[x+1]:
      visited[x+1] = True
      q.append((x+1,cnt+1))
    if 0 <= x*2 <= 100000 and not visited[x*2]:
      visited[x*2] = True
      q.append((x*2,cnt))

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

visited = [False] * 100001
print(bfs(n))

- 아래 코드처럼 x*2로 이동할 경우 appendleft 로 큐에 삽입해주니 해결 

- 틀린 이유를 찾느라 시간이 오래 걸렸다. 

 from collections import deque 

def bfs(n):
  visited[n] = True

  q= deque()
  q.append((n,0))

  while q:
    x, cnt = q.popleft()

    if x == k:
      return cnt

    if 0 <= x*2 <= 100000 and not visited[x*2]:
      visited[x*2] = True
      q.appendleft((x*2,cnt))
    if 0 <= x-1 <= 100000 and not visited[x-1]:
      visited[x-1] = True
      q.append((x-1,cnt+1))
    if 0 <= x+1 <= 100000 and not visited[x+1]:
      visited[x+1] = True
      q.append((x+1,cnt+1))
    

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

visited = [False] * 100001
print(bfs(n))