[알고리즘_코딩 테스트_JAVA] 그래프-물의 양 구하기 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

✔ 문제 049 물의 양 구하기

문제 바로가기 💨 

 

⬜ 핵심 아이디어

• A,B,C 의 물의 양 상태를 1개의 노드로 가정하고 줄기 노드를 모두 탐색한다.
• 노드에서 갈 수 있는 6개의 경우(A->B, A->C, B->A, B->C, C->A, C->B) 노드를 BFS 탐색한다 (큐 추가).
• 이때, a,b,c 물의양이 동일한 노드에 방문한 이력이 있을때는 큐에 추가하지않는다.
• 받는 물통에 보내는 물통의 모든 용량을 저장한다.보내는 물통에는 0을 저장한다.
• 만약 받는 물통이 넘친다면 그 초과 양만큼 보내는 물통에 남긴다.
• 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 3번째 물통(C)의 값을 정답 리스트에 추가한다.

 

수도 코드

---

JAVA

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    // 6가지 이동 케이스 표현 배열
    static int[] sender = {0, 0, 1, 1, 2, 2};
    static int[] receiver = {1, 2, 0, 2, 0, 1};
    static boolean visited[][]; // A,B의 무게만 있으면 C의 무게가 고정되므로 2개만 체크
    static boolean answer[];
    static int now[];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        now = new int[3]; // A,B,C 물의 양 저장 배열
        now[0] = sc.nextInt();
        now[1] = sc.nextInt();
        now[2] = sc.nextInt();
        visited = new boolean[201][201];
        answer = new boolean[201];
        BFS();
        for (int i = 0; i < answer.length; i++) {
            if (answer[i]) System.out.print(i + " ");
        }
    }

    public static void BFS() {
        Queue<AB> queue = new LinkedList<>();
        queue.add(new AB(0,0));
        visited[0][0] = true;
        answer[now[2]] = true;
        while (!queue.isEmpty()) {
            AB p = queue.poll();
            int A = p.A;
            int B = p.B;
            int C = now[2] - A - B; // C는 전체 물의 양에서 A와 B를 뺀 것
            for(int k = 0; k < 6; k++){
                int[] 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 (!visited[next[0]][next[1]]) { // A와 B의 물의 양을 이용해 방문 체크
                    visited[next[0]][next[1]] = true;
                    queue.add(new AB(next[0],next[1]));
                    if(next[0]==0){ // A의 물의 양이 0일 때 C의 물의 무게를 정답 변수에 저장
                        answer[next[2]] = true;
                    }
                }
            }
        }
    }

    // AB 클래스 선언 -> A와 B의 값만 지니고 있으면 C는 유추할 수 있으므로 두 변수만 사용하기
    static class AB {
        int A;
        int B;
        public AB(int A,int B){
            this.A = A;
            this.B = B;
        }
    }
}

PYTHON

from collections import deque
# 두 리스트를 이용해 6가지 이동 케이스 정의
# 0,1,2는 각각 A,B,C 물통을 뜻함

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():
    q = deque()
    q.append((0,0))
    visited[0][0] = True
    answer[now[2]] = True
    
    while q:
        n = q.popleft()
        A, B = n[0],n[1]
        C = now[2] - A - B # C는 전체 물의 양에서 A와 B를 뺀 것
        for k in range(6): # A->B, A->C, B->A, B->C, C->A, C->B
            next = [A, B, C] # 현재 물의양 상태
            next[receiver[k]] += next[sender[k]] # 받는 물통에 보내려는 물통 값 더하기
            next[sender[k]] = 0 # 보내는 물통 값 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
                q.append((next[0],next[1]))
                if next[0] == 0: # A의 물의 양이 0일 때 C의 물의 양을 정답에 저장
                    answer[next[2]] = True
bfs()

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