049 물통

첫번째 코드

 

어렵다...접근 방법조차 잘 모르겠어서 책을 참고했다.

이런 종류의 트리도 있구나~ 라는 생각이 들었다.

 

코드는 책을 참고했다.

 

import sys
from collections import deque

sender = [0, 0, 1, 1, 2, 2]
receiver = [1, 2, 0, 2, 0, 1]
now = list(map(int, input().split()))
visited = [[False for j in range(201)] for i in range(201)]
answer = [False] * 201

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

    while queue:
        now_node = queue.popleft()
        a = now_node[0]
        b = now_node[1]
        c = now[2] - a - b

        for k in range(6):
            next = [a, b, c]
            next[receiver[k]] += next[sender[k]]
            next[sender[k]] = 0

            if next[receiver[k]] > now[receiver[k]]:
                next[sender[k]] = next[receiver[k]] - now[receiver[k]]
                next[receiver[k]] = now[receiver[k]]
            
            if not visited[next[0]][next[1]]:
                visited[next[0]][next[1]] = True
                queue.append((next[0], next[1]))

                if next[0] == 0:
                    answer[next[2]] = True

BFS()

for i in range(len(answer)):
    if answer[i]:
        print(i, end = ' ')

 

통과!

 

이해가 어려워 수도코드를 추가한다.

근데 왜 봐도 어려운 기분이 들지? ㅋㅋㅋㅋㅋ

 

sender, receiver (6가지 경우를 탐색하기 위한 리스트)

now (a, b, c값 저장)

visited (방문 여부 저장 리스트)

answer (정답 리스트)

 

# BFS 구현하기

BFS:

    큐 자료구조에 출발 노드 더하기 -> a와 b가 0인 상태이므로 0, 0노드에서 시작하기

    visited 리스트에 현재 노드 방문 기록

    answer 리스트에 현재 c의 값 체크

    

    while 큐가 빌 때까지:

        큐에서 노드 데이터 가져오기

        데이터를 이용해 a, b, c 값 초기화

 

        for 6가지 케이스 반복:

             받는 물통에 보내려는 물통의 값 더하기

              보내려는 물통의 값을 0으로 업데이트하기

 

              if 받는 물통이 넘칠 때:

                   넘치는 만큼 보내는 물통에 다시 넣어 주고 받는 물통은 이 물통의 최댓값으로 저장

                   

                   if 현재 노드의 연결 노드 중 방문하지 않은 노드:

                        큐에 데이터 삽입

                        visited 리스트에 방문 기록

 

                        if 1번째 물통이 비어 있을 때:

                             3번째 물통의 물의 양을 answer 리스트에 기록

 

BFS 수행

 

for answer 리스트 탐색:

    answer 리스트에서 값이 true인 index를 정답으로 출력

 

다음에도 풀어보도록 하자!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/2251.%E2%80%85%EB%AC%BC%ED%86%B5

programmers/백준/Gold/2251. 물통 at main · ornni/programmers