[BOJ] 12851. 숨바꼭질2 (🥇, BFS/DFS)

문제

풀이1(220ms)

1. 같은 깊이의 큐에 있는 경우는 방문했던 곳을 한 번 더 재방문할 수 있게 해준다.
2. visit[x][1]은 여기까지 오는 경로가 몇 가지였느냐(경우의 수)를 나타내며 최종적으로 여기에 방문하는 모든 경우의 수를 다 더한 값을 나타내야 하므로(총합) 추가적으로 계속 더해줘야 한다. 이 부분을 +1로 설정해서 오류 발생

from collections import deque

def bfs():
    q = deque([N])
    visit[N] = [1, 1]
    while q:
        X = q.popleft()
        if X == K:
            return visit[X][0] -1, visit[X][1]
        for x in (X - 1, X + 1, 2 * X):
            if -1 < x < 100001:
                # print(x, visit[:10])
                if visit[x][0] == 0:
                    visit[x][0] = visit[X][0] + 1
                    visit[x][1] = visit[X][1]
                    q.append(x)
                # 재방문 가능: 같은 깊이의 큐에서 방문했을 경우! visit[X][0]은 결국 깊이를 나타내기 때문
                elif visit[x][0] == visit[X][0] + 1:					
                	# 여기까지 오기 위해 거쳤던 경로가 visit[X][1]에 저장되어 있으며 이 값들의 총합을 visit[x][1]에 저장해야 한다. 추가적으로 계속 더해줘야 함
                    visit[x][1] += visit[X][1]

N, K = map(int, input().split())
visit = [[0, 0] for _ in range(100001)]

print('\n'.join(map(str, bfs())))

풀이2(128ms)

1. N > K 인 경우는 무조건 -1 하는 방식 밖에 없기 때문에 경로는 N - K, 방식은 하나다. N == K 인 경우도 동일하므로 예외처리로 빼준다
2. 같은 깊이에 위치한 큐가 한 번 돌고 나면 자동으로 종료되고 그 큐에서 얻어낸 다음 위치의 값이 들어있는 큐로 갱신시켜준다. 이 경우 같은 깊이의 큐에서는 재방문이 가능하도록 방문처리는 큐가 종료된 후 일괄적으로 처리한다. depth는 큐가 한 번 돌 때마다 1씩 추가한다.
3. 최종적으로 depth와 visit[K] 값만 출력하면 된다.

def bfs():
    global depth
    start = [N]
    while 1:
        for s in start:
            visit[s] += 1
        if visit[K] != 0:
            break
        depth += 1
        q = []
        for s in start:
            if s - 1 > 0 and visit[s - 1] == 0:
                q.append(s - 1)
            if s + 1 < 100001 and visit[s + 1] == 0:
                q.append(s + 1)
            if s * 2 < 100001 and visit[s * 2] == 0:
                q.append(s * 2)
        start = q

N, K = map(int, input().split())
depth = 0
visit = [0] * 100001

if N >= K:
    print(N - K)
    print(1)
else:
    bfs()
    print(depth)
    print(visit[K])

반례

5 237
10
5

---

1 3
2
2

---

1 4
2
2

---

1 7
4
4

후기

• 같은 깊이에서는 재방문이 가능하게 해야 함

---

풀이3(76ms, 복습)

가장 빠른 시간과 가장 빠른 방법의 개수

기본적으로 너비 우선 탐색은 탐색의 범위를 한 단계씩 넓혀가면서 탐색하는 방식이다. 코드상으로는 큐에서 원소를 하나씩 꺼내서 사용하는 방식처럼 보이지만 기준이 되는 단계(1초, 또는 거리1)에 따라 큐가 단계별로 나뉠 수 있다.

만약 1부터 탐색을 시작한다면 시간이 증가함에 따라 큐에 담기게 되는 숫자는 아래와 같다.

"""
1. 이전에 큐에 한 번이라도 담겼던 숫자는 제외(방문 처리)
2. 0보다 크고 10만보다 작은 숫자만 
"""

# 0초
queue = [1]

# 1초
queue = [2, 2]

# 2초
queue = [3, 4, 3, 4]

# 3초
queue = [6, 5, 8, 6, 5, 8]

만약 찾으려는 K의 값이 8이라면 각 단계별로 큐를 탐색하다가 8이란 숫자가 처음 등장했을 때, 그때의 초(가장 빠른 시간)와 큐에 담겨있는 8의 개수(가장 빠른 방법의 개수)를 구하면 된다.

단, 이때 이미 이전에 한 번 큐에 한 번이라도 있었던 값은 다음 큐에서 중복탐색하면 시간초과가 발생하므로 따로 방문처리를 해줘야 한다. 주의해야할 점은 큐를 탐색하는 도중에 방문처리를 해주게 되면 방법의 개수를 구할 수 없다. 방법의 개수는 현재 단계에서 중복되는 숫자를 전부다 구할 수 있어야 한다. 그래서 방문처리는 단계별 큐 탐색이 끝난 후 마지막에 한꺼번에 처리한다.

1초를 기준 단계로 탐색하기 때문에 시간에 대한 정보는 따로 큐에 추가할 필요 없이 큐 탐색이 끝날때마다 1씩 증가시켜준다.

# 숨바꼭질 2

N, K = map(int, input().split())

def sol():
    if N >= K:
        return N-K, 1

    queue = [N]
    time = 0
    visited = [0]*100001
    visited[N] = 1
    while queue:
    
        new_q = []
        for x in queue:
            for y in (x-1, x+1, 2*x):
                if y<0 or y>100000 or visited[y]:
                    continue

                new_q.append(y)

        time += 1
        # K를 발견했다면 최단 시간과 방법의 개수 출력
        if K in new_q:
            return time, new_q.count(K)
    	
        # 이전 단계의 큐 방문처리
        for x in new_q:
            visited[x] = 1
        queue = new_q[:]

result = sol()
print('\n'.join(map(str, result)))