[Algorithm] 2251번 - 물통

sunny·2024년 8월 24일

BFS DFS

algorithm

목록 보기

3/7

문제

BFS

BFS를 주로 사용하는 문제 유형

최단 경로 찾는 문제
BFS는 모든 노드를 동일한 거리 순으로 탐색하기 때문에 처음 목표 노드에 도달했을 때의 경로가 최단 경로임이 보장된다.
ex. 미로 탐색, 최단 경로 구하기 등
영역 채우는 문제
인접한 모든 노드를 탐색하여 연결된 모든 영역을 효율적으로 탐색할 수 있다.
ex. 토마토 모두 익히는 최단 경로, 색상 영역 채우기 등
트리구조에서 각 레벨별로 탐색하는 문제
BFS는 각 레벨을 순서대로 탐색하므로, 레벨 단위의 탐색에 적합하다.
ex. 각 레벨에 있는 노드의 개수 세기
결합 가능한 모든 상태를 탐색하는 문제
여러 상태를 조합하여 가능한 모든 경우(상태)를 탐색하는 문제에 효과적이다.
ex. 물통 문제, 숫자 조합 문제 등
그래프에서 연결된 구성요소의 개수를 찾거나 구성요소를 탐색하는 문제
BFS는 한 노드에서 시작해서 연결된 모든 노드를 탐색할 수 있으며, 이를 통해 연결된 구성요소를 찾을 수 있다.
ex. 구성요소 개수 찾는 문제, 그래프에서 연결된 서브 그래프 찾기 등
2D 배열에서 탐색 문제
2차원 격자에서 인접한 모든 방향(상하좌우)를 탐색하여 요소들을 효율적으로 탐색할 수 있다.
ex. 이동 가능한 영역 찾기, 미로의 출구 찾기 등

BFS 🆚 DFS

풀이법

BFS는 너비 우선 탐색으로 시작 노드에서 가까운 노드를 먼저 탐색하며 각 레벨 순서대로 탐색한다. 큐와 반복문을 사용하여 구현한다.
DFS는 깊이 우선 탐색으로 시작 노드에서 가능한 깊이까지 탐색한 후, 다시 돌아와 다른 경로를 탐색한다. 스택 또는 재귀를 사용하여 구현한다.

BFS만 적합한 문제

최단 경로 문제 : 각 노드를 균등하게 탐색하기 때문에 항상 최단 경로를 먼저 찾는다.
영역 채우는 문제, 2D 배열 탐색 문제 : 그래프나 2D 배열에서 연결된 모든 영역을 효율적으로 탐색할 수 있다.

DFS만 적합한 문제

모든 경로 찾기 문제 : 경로가 매우 깊거나 모든 경로를 완벽하게 탐색해야 하는 경우 더 유리하다.
ex. 미로에서 출구 찾기 위해 모든 경로를 탐색해야 할 때, 특정 조건을 만족하는 경로 찾기 등
백트래킹 문제 : 상태를 하나씩 확장하면서 조건을 만족하지 않으면 이전 상태로 돌아가는 방식
ex. N-Queen (체스) 문제, 퍼즐 문제 (스도쿠), 조합 및 순열 생성 등
그래프 사이클 탐지 문제

BFS, DFS 함께 사용할 수 있는 문제

그래프 탐색, 임의의 경로 탐색 : 두 방법 모두 사용할 수 있지만 탐색 목적에 따라 선택하면 된다.
- BFS는 최단 경로를 빨리 찾을 때 유리
- DFS는 가능한 모든 경로를 탐색하는 데 유리, 사이클 탐지에도 많이 사용된다.

풀이 방법

결합 가능한 모든 상태를 탐색하는 문제이므로 BFS를 사용하여 문제를 풀었다.

bfs에서 반복문과 큐로 풀기 위해서 물통의 용량, 현재 물의 양을 리스트 형태로 저장하고 배열로 접근한다.
인접한 모든 방향 (어느 물통에서 어느 물통으로 물을 이동시킬지)을 고려하기 위해 주는 방향의 물통의 인덱스를 _from 리스트에 저장하고, 받는 방향의 물통 인덱스를 _to 리스트에 저장하여 모든 경우의 수를 고려할 수 있다.

정답 코드

# BFS - 2251번 - 물통
## BFS가 가능한 이유 : 1.물통의 모든 상태를 고려해야 함 2.물을 나눠담는 조합의 경우의 수 = 200^3
from collections import deque
from copy import deepcopy
bucket = list(map(int, input().split()))		# 물통 A, B, C의 용량
result = [[0] * (bucket[1] + 1) for _ in range(bucket[0] + 1)]
# result[a][b] = 물통A에 a가 들어있고, 물통B에 b가 들어있을 때, 물통C에 들어있는 물의 양

_from = [0, 0, 1, 1, 2, 2]
_to = [1, 2, 0, 2, 0, 1]

q = deque()
q.append([0, 0, bucket[2]])
result[0][0] = 1
s = set()

while len(q) > 0:
    cur = q.popleft()
    if cur[0] == 0:
        s.add(bucket[2]-cur[1])
    for i in range(6):
        f, t = _from[i], _to[i]
        next = deepcopy(cur)
        if cur[f] < bucket[t]-cur[t]:     # case 1) 물을 주는 통(from)에 남아있는 걸 다 주기
            next[f] = 0
            next[t] += cur[f]
        else:                             # case 2) 물을 넣는 통(to)을 꽉 채우기
            next[f] -= bucket[t]-cur[t]
            next[t] = bucket[t]
        if result[next[0]][next[1]] == 0:
            result[next[0]][next[1]] = 1
            q.append(next)


ans = sorted(list(s))
for i in ans:
    print(i, end=' ')