[백준] 2251번 : 물통 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2251번: 물통

 

1. 문제 설명

2. 풀이과정

지금까지 접해 봤던 그래프 데이터를 저장하고 저장한 자료구조를 이용하는 방식과 달리, 그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이다.

A, B, C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 에지로 이어진 인접한 노드라고 생각하고 문제를 해결하면 된다.

 

처음에는 물통 A, B가 비어 있고, 물통 C는 꽉 차있는 상태이므로 해당 상태에서 탐색을 시작한다.

BFS 알고리즘을 활용하여 탐색을 수행한다.

BFS 알고리즘의 수행 과정은 우선 해당 노드에서 변경할 수 있는 경우는 총 6가지(A→B, A→C, B→A, B→C, C→A, C→B)가 있다.

6가지 경우를 각각 탐색하며 A, B, C 무게가 동일한 노드가 아닐 경우에는 큐에 추가한다.

다음 노드를 큐에 저장할 때 만약 해당 노드 물통 A의 무게가 0이면 정답 리스트에 해당 노드 물통 C의 무게를 추가한다.

정답 리스트를 오름차순으로 출력한다.

 

슈도코드

1. A, B, C 값 입력받기
2.  size(A, B, C 물통의 크기 저장)
3. BFS 구현하기 BFS():
   1. queue 자료구조 생성 후, 시작 노드인 [0, 0, C] 추가
   2. visited 리스트에 시작 노드 방문 기록(리스트에 노드 추가)
   3. answer 리스트에 현재 물통 C의 무게 추가 (물통 A의 무게가 0이므로)
   4. while (queue가 빌 때까지):
      1. now(queue에서 현재 노드 데이터 가져오기)
      2. for 6가지 경우 반복:
         1. next(다음 노드 결과를 저장할 노드, 우선 now 노드 복사)
         2. if (시작 위치의 물통에 옮길 물이 있으면):
            1. 물통의 물을 전부 옮기고 시작 위치의 물통은 비움
            2. if (옮긴 물이 물통의 크기를 넘어가면): 물통 크기만큼만 채우고 나머지는 다시 시작 물통에 담음
         3. if (다음 노드가 아직 방문하지 않은 노드이면):
            1. queue에 다음 노드 추가
            2. if (물통 A의 무게가 0이고 정답 리스트에 아직 추가하지 않은 무게이면): 물통 C의 무게를 추가
            3. visited 리스트에 다음 노드 방문 기록
   5. move(다음 노드로 가능한 경우 6가지 저장)
   6. visited(방문 여부 저장 리스트)
   7. answer(정답 리스트)
   8. BFS 수행
   9. answer 리스트 오름차순으로 정렬
   10. for answer 리스트: 각 원소 출력

반응형

3. 소스코드

import sys
from collections import deque

A, B, C = map(int, sys.stdin.readline().split())

size = [A, B, C]

def BFS():
    queue = deque()
    queue.append([0, 0, C])
    visited.append([0, 0, C])
    answer.append(C)

    while (queue):
        now = queue.popleft()
        for s, e in move:
            next = [i for i in now]

            if (next[s] > 0):
                next[e] += next[s]
                next[s] = 0
                if (next[e] > size[e]):
                    next[s] += next[e] - size[e]
                    next[e] = size[e]

            if (next not in visited):
                queue.append(next)
                if (next[0] == 0) and (next[2] not in answer):
                    answer.append(next[2])

                visited.append(next)


move = [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]]
visited = []
answer = []

BFS()

answer.sort()
for i in answer:
    print(i, end=' ')