[DFS/BFS/완전탐색] ★ 13549번 - 숨바꼭질 3(BFS)

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

풀이 시간: 15~20분 이내

2가지 풀이 방법이 있으나 2번 풀이가 문제를 본질적으로 이해하고 효율적으로 짠 코드이기 때문에 이렇게 구현하는 것이 바람직하다.

 

유사 문제: 1697번, 12851번

https://hseungyeon.tistory.com/222

[DFS/BFS/완전탐색] 1697번 - 숨바꼭질(BFS)

https://hseungyeon.tistory.com/229

[DFS/BFS/완전탐색] ★ 12851번 - 숨바꼭질 2(BFS)

 

(풀이1) 가중치를 고려하지 않고 모든 경우의 수를 검사하는 방법

1) 문제 해결 아이디어

이전 문제와 거의 비슷한 문제로 이번 문제는 x -1, x + 1 은 1초가 걸리고 2 * x 는 0초가 걸린다는 새로운 조건이 있다. 이러한 전제 하에 시작점에서 끝점까지 도달하는 최소 시간 즉, 최단 경로를 구하는 문제로 BFS로 풀어야 한다.

 

이전 문제처럼 이 문제 또한 끝점(k)에 도달할 수있는 방법이 여러개 일 수 있으므로 큐에서 값을 꺼낸 후에 방문 처리를 한다. 경우에 따라 소요시간의 차이로 인하여 처음 발견한 것보다 나중에 발견한 것이 더 빠를 수 있기 때문에 끝 점(k)에 도달한 경우 최소 시간을 업데이트해주어야 한다. 현재 시간(cnt)이 최소 시간(min_time)보다 작다면 최소 시간을 변경해주고 종료 시 최소 시간을 리턴한다.

 

2) 소스코드

from collections import deque

# BFS
def bfs(x, cnt):
  min_time = 1e9	# 최소 시간
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, cnt))
  visited[x] = 1
  
  while queue:
    x, cnt = queue.popleft()
    visited[x] = 1

    # 끝 값에 도달하면
    if(x == k):
      # 처음 발견하면
      if(cnt < min_time):
        min_time = cnt
      
    dx = [x - 1, x + 1, 2 * x]
    for i in range(3):
      nx = dx[i]
      if(0 <= nx <= 100000):
        # 방문한적이 없으면
        if(visited[nx] == 0):
          if(i == 2):
            queue.append((nx, cnt))            
          else:
            queue.append((nx, cnt + 1))
  return min_time

n, k = map(int, input().split())  # 시작 위치, 끝 위치
visited = [0] * 100001
print(bfs(n, 0))

 

(풀이2) 우선순위를 고려한 효율적인 방법

1) 문제 해결 아이디어

여기서 중요한 점은 값을 증가시킬 수 있는 2 * x 와 x + 1 은 각각 0초, 1초가 걸리므로 2 * x 를 먼저 하도록 하는 것이 유리하다. 즉, 2 * x를 먼저 하도록 했을 때 끝 값(k)에 도달하면 그게 바로 최소 시간이 된다.

 

2) 소스코드

from collections import deque

# BFS
def bfs(x, cnt):
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, cnt))
  visited[x] = 1
  
  while queue:
    x, cnt = queue.popleft()
    visited[x] = 1

    # 끝 값에 도달하면
    if(x == k):
      return cnt
      
    for nx in [2 * x, x - 1, x + 1]:
      if(0 <= nx <= 100000):
        # 방문한적이 없으면
        if(visited[nx] == 0):
          if(nx == 2 * x):
            queue.append((nx, cnt))            
          else:
            queue.append((nx, cnt + 1))

n, k = map(int, input().split())  # 시작 위치, 끝 위치
visited = [0] * 100001
print(bfs(n, 0))

[참고] https://tooo1.tistory.com/462

[백준(BOJ)] 13549번 : 숨바꼭질 3 - PYTHON[파이썬]