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

[백준] 12851번 - 숨바꼭질 2

풀이 시간: 60분 이내

유사문제 1697번 

https://hseungyeon.tistory.com/222

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

 

1) 문제 해결 아이디어

알고리즘을 짜는 것 자체는 20분 정도 걸렸는데 오류를 고치는데 시간이 오래 걸린 문제로 계속 모르겠어서 검색을 통해 해결했다. 추후 복습이 꼭 필요한 문제!!

 

이 문제는 시작, 끝 위치가 주어졌을 때, 시작위치에서 끝위치까지 도달할 수 있는 최소 시간을 구하는 최단경로 문제로 BFS로 풀어야 한다. 하지만 약간 다른 점이 있다면 최소 시간이 되는 방법수를 추가적으로 구해야한다는 것이다.

원래 보통의 문제들은 목표값에 도달하면 바로 값을 리턴하고 종료하지만 이 문제의 경우에는 방법수를 구해야하므로 추가적인 조건 검사가 필요하다.

 

첫번째 오류. 메모리 초과

보통 문제들처럼 방문한적이 없으면 큐에 삽입, 방문처리를 둘 다 했는데 문제가 발생했다.

이 문제에서는 방문한적이 없는 경우 큐에 삽입만하고 방문 처리는 값을 꺼낼 때 해야한다.

 

Q. 값을 꺼낼 때 방문 처리를 해야하는 이유는?

예를 들어, 시작값: 1, 목표값: 10 이라고 하자.

1 → 10 최소 시간은 4이고 방법은 2가지가 있다.

1) 1 (+1) 2 (*2) 4 (+1) 5 (*2) 10

2) 1 (*2) 2 (*2) 4 (+1) 5 (*2) 10

 

만약 큐에 삽입을 하고 방문처리를 바로 한다면 동일한 값에 방문할 수 없는 문제가 발생한다. 

1)번 방법에서 +1을 하여 2를 만들고 큐에 삽입, 방문 처리를 하면

2)번 방법에서 *2를 하여 2를 만들어야 하지만 2는 이미 방문 처리가 되어있기 때문에 방문할 수 없게된다.

 

그러므로 방문한적이 없으면 큐에 삽입만 하고 방문 처리는 값을 꺼내고 난 후에 해야한다!!!

 

[참고] https://dalseoin.tistory.com/entry/%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-12851-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-2

[백준-파이썬] 12851: 숨바꼭질 2

 

2) 소스코드

from collections import deque

# BFS
def bfs(x, cnt):
  min_time = 0  # 최소 시간
  num = 0       # 방법수
  queue = deque()
  # 시작 위치 삽입, 방문처리
  queue.append((x, cnt))
  visited[x] = 1
  
  while queue:
    x, cnt = queue.popleft()
    visited[x] = 1  # 방문 처리
    # 동생을 찾으면 종료
    if(x == k):
      # 처음 발견하면
      if(min_time == 0):
        min_time = cnt  # 최소시간 설정
        num += 1        # 방법수 카운트
      # 2번째 이상 발견한 시간이 최소시간과 같다면 
      elif(min_time == cnt):
        num += 1        # 방법수 카운트만
      # 2번째 이상 발견한 시간이 최소시간과 다르면(최소시간보다 무조건 크므로) 종료
      else:   break 

    for nx in [x - 1, x + 1, 2 * x]:
      if(0 <= nx <= 100000):
        # 방문한적이 없으면
        if(visited[nx] == 0):
          queue.append((nx, cnt + 1))  # 삽입만
  return (min_time, num)  # 종료 시 최소 시간, 방법수 리턴
  
n, k = map(int, input().split())  # 수빈, 동생 위치
visited = [0] * (100001)
for i in bfs(n, 0):
  print(i)