[백준, Java] 2251번, 물통(그래프 탐색)

문제 링크

2251번: 물통

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 물통 A, B, C가 존재하며, 초기에는 C에만 물이 가득 채워져있습니다.

2. 각 물통에 있는 물을 다른 물통에 옮길 수 있으며, 가득 채우거나, 모두 옮겼을 때 행동이 중단됩니다.

3. A가 비워있을 때 C 물통에 존재하는 물의 양들을 오름차순 정렬하여 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS을 통해서 물을 옮기는 과정을 진행합니다.(중복된 탐색은 제외)

 

3. 탐색을 통해 얻은 A의 물의 양이 0일 때 C의 물의 양들을 오름차순으로 정렬해서 결과로 출력합니다.

 

 

물 옮기기(그래프 탐색)

 

물을 옮길 때에는 6가지 경우의 수가 존재합니다.

 

A	→	B
A	→	C
B	→	A
B	→	C
C	→	A
C	→	B

 

물을 옮기는 과정을 모두 탐색해서 A의 물의 양이 0일 때 C의 양의 개수를 탐색할 것입니다.

 

하지만, 완전 탐색을 진행한다면 순서는 바뀌었지만 동일한 탐색이 발생합니다.

→순서는 바뀌었지만, A, B, C 물통의 양이 이미 탐색한 양인 경우

 

동일한 탐색을 방지하기 위해서 boolean[][][]으로 중복된 탐색인 경우를 방지하였습니다.

 

boolean[i][j][k]

 

i = A 물의 양

 

j = B 물의 양

 

k = C 물의 양

 

boolean[20][20][30] = A의 물의 양이 20, B의 물의 양 20, C의 물의 양 30일 때를 탐색하였다.

 

또한, 물통의 최대 값이 200으로 boolean[201][201][201]으로 초기화를 진행하였습니다.

 

이후, 물을 옮기는 모든 경우에 대한 과정은  BFS을 통해서 진행되도록 하였습니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

 

물통 정보

 

A	B	C
8	9	10

 

 

 

 

2. BFS을 통해서 물을 옮기는 과정을 진행합니다.(중복된 탐색은 제외)

 

 

 

초기 물통



A	B	C
0	0	10

= A가 0일 때 C의 값 10이 존재한다. (boolean[0][0][10] = true)

 

 

C → B

A	B	C
0	9	1

= A가 0일 때 C의 값 1이 존재한다.(boolean[0][9][1] = true)

 

C → A → B

A	B	C
0	8	2

= A가 0일 때 C의 값 2이 존재한다.(boolean[0][8][2] = true)

 

....

 

 

 

3. 탐색을 통해 얻은 A의 물의 양이 0일 때 C의 물의 양들을 오름차순으로 정렬해서 결과로 출력합니다.

 

10 1 2 8 9이 존재합니다.

 

오름차순으로 정렬하면 아래와 같이 결과를 출력합니다.

 

 

1 2 8 9 10결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용해서 물통의 정보를 띄어쓰기 기준 나누었습니다.
• BFS를 통해서 물을 옮기는 모든 과정을 진행하였습니다.
• TreeSet<>을 통해서 A가 0일 때 C 물통의 양을 오름차순으로 정렬되도록 하였습니다.
• 물 옮기는 과정 이후, TreeSet에 대한 C의 정보를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• bfs 함수는 BFS을 통해서 물을 옮기는 과정을 진행하였습니다.
• checkWate 함수는 중복된 탐색인지 확인한 뒤 BFS Queue을 넣는 과정을 진행합니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
    //물 옮기는 과정에서 A, B, C에 대한 양을 정의하는 Class
    static class Water{
        int A, B, C;
        public Water(int a, int b, int c) {
            A = a;
            B = b;
            C = c;
        }
    }
    //A가 0일 때 C의 물의 양을 저장하는 TreeSet
    static TreeSet<Integer> result = new TreeSet<>();
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //물통의 정보 저장
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        //물 옮기는 경우 탐색 진행
        bfs(A, B, C);
        //A가 0일 때 C의 물의 양 오름차순 BufferedWriter 저장
        for(int L : result){
            bw.write(String.valueOf(L));
            bw.write(" ");
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 통해서 물을 옮기는 과정 진행하는 함수
    static void bfs(int A, int B, int C){
        //BFS을 사용할 Queue
        Queue<Water> q = new ArrayDeque<>();
        boolean[][][] visited = new boolean[201][201][201];
        q.offer(new Water(0, 0, C));
        //초기 물의 양 저장
        visited[0][0][C] = true;
        //물 옮기는 과정 진행
        while(!q.isEmpty()){
            Water cur = q.poll();
            //A의 물의 양이 0일 때
            if(cur.A == 0){
                result.add(cur.C);
            }
            int tempA, tempB, tempC;
            //A → B
            tempA = cur.A - Math.min(cur.A, B-cur.B);
            tempB = cur.B + Math.min(cur.A, B-cur.B);
            tempC = cur.C;
            checkWater(visited, tempA, tempB, tempC, q);
            
            //A → C
            tempA = cur.A - Math.min(cur.A, C-cur.C);
            tempB = cur.B;
            tempC = cur.C + Math.min(cur.A, C-cur.C);
            checkWater(visited, tempA, tempB, tempC, q);
            
            //B → A
            tempA = cur.A + Math.min(cur.B, A-cur.A);
            tempB = cur.B - Math.min(cur.B, A-cur.A);
            tempC = cur.C;
            checkWater(visited, tempA, tempB, tempC, q);
            
            //B → C
            tempA = cur.A;
            tempB = cur.B - Math.min(cur.B, C-cur.C);
            tempC = cur.C + Math.min(cur.B, C-cur.C);
            checkWater(visited, tempA, tempB, tempC, q);

            //C → A
            tempA = cur.A + Math.min(cur.C, A-cur.A);
            tempB = cur.B;
            tempC = cur.C - Math.min(cur.C, A-cur.A);
            checkWater(visited, tempA, tempB, tempC, q);

            //C → B
            tempA = cur.A;
            tempB = cur.B + Math.min(cur.C, B-cur.B);
            tempC = cur.C - Math.min(cur.C, B-cur.B);
            checkWater(visited, tempA, tempB, tempC, q);
        }
    }

    //중복된 탐색인지 확인한 뒤에 BFS에 대한 Queue을 저장하는 함수
    private static void checkWater(boolean[][][] visited, int tempA, int tempB, int tempC, Queue<Water> q) {
        if(!visited[tempA][tempB][tempC]){
            visited[tempA][tempB][tempC] = true;
            q.offer(new Water(tempA, tempB, tempC));
        }
    }
}