[BOJ - JAVA] 2251 - 물통 (BFS)

# 주소

https://www.acmicpc.net/problem/2251

2251번: 물통

# 문제

# 문제 해설 및 코드 리뷰

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

public class Main {
    static int dir[][] = {{0,1},{0,2},{1,0},{1,2},{2,0},{2,1}};
    static int[] arr = new int[3];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        for(int i = 0; i < 3; i++)
            arr[i] = scan.nextInt();
        int sum = arr[2];
        boolean[][] visit = new boolean[201][201];
        boolean[] ans = new boolean[201];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        queue.offer(0);
        visit[0][0] = true;
        ans[arr[2]] = true;
        while (!queue.isEmpty()) {
            int temp[] = new int[3];
            temp[0] = queue.remove();
            temp[1] = queue.remove();
            temp[2] = sum - temp[0] - temp[1];
            for(int k = 0; k < 6; k++){
                int next[] = {temp[0], temp[1], temp[2]};
                next[dir[k][0]] += next[dir[k][1]];
                next[dir[k][1]] = 0;
                if(next[dir[k][0]] >= arr[dir[k][0]]){
                    next[dir[k][1]] = next[dir[k][0]] - arr[dir[k][0]];
                    next[dir[k][0]] = arr[dir[k][0]];
                }
                if(!visit[next[0]][next[1]]){
                    visit[next[0]][next[1]] = true;
                    queue.offer(next[0]);
                    queue.offer(next[1]);
                    if(next[0] == 0){
                        ans[next[2]] = true;
                    }
                }
            }
        }
        for(int i = 0; i <= arr[2]; i++){
            if(ans[i])
                System.out.print(i + " ");
        }
    }
}

DFS 문제 분류에서 고른 문제인데 풀고보니까 BFS네요.

둘의 차이는 시간복잡도 측면에서 n개의 값이 비교적 적다면 BFS가 유리하고 n개의 값이 많을수록 DFS가 유리합니다.

그것에 관해 옛날에 포스팅을 한 적이 있는데 이게 또 문제마다 조금씩 달라서 저는 웬만해서는 BFS로 푸는 편입니다.

 

문제를 해석해봅시다.

 

A, B, C라는 물통이 있는데 A의 물통이 비어져있을 때 나올 수 있는 C의 값을 모두 출력하는 것이 문제입니다.

따라서 순열, 조합으로 풀어도 되지만 방향 벡터 종류가 총 6가지 밖에 되지 않기 때문에 BFS로 풀어봅시당

static int dir[][] = {{0,1},{0,2},{1,0},{1,2},{2,0},{2,1}};
static int[] arr = new int[3];

dir의 저 숫자 값들은 2차원으로 선언하는걸 좋아해서 전 이렇게 구성했습니다.

저기서 0,1이 의미하는 것은 arr[0]에서 arr[1]로 물을 붓는다 이렇게 생각하시면 되겠습니다.

앞에 나와 있는 파라미터는 ~로부터, 뒤에 있는 파라미터는 ~에게 즉, to - from의 관계에 있다 볼 수 있습니다.

arr는 3의 크기를 가지는 배열로 선언하겠습니다.

boolean[][] visit = new boolean[201][201];
boolean[] ans = new boolean[201];
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
queue.offer(0);
visit[0][0] = true;
ans[arr[2]] = true;

그리고 visit은 2차원, ans는 1차원으로 선언하여 중복되는 부분을 재탐색하지 않도록 선언합니다.

나중에 왜 이것이 필요한지 다시 확인해봅시다.

BFS를 풀 때에는 Queue를 주로 사용합니다.

안써도 되는 문제도 있지만 BFS방식은 새로 탐색한 인덱스에 대해 주변 인덱스를 탐색하는 것이 특징이므로 Queue에 넣었다 뺐다 자유자재로 쓸 수 있다면 이것보다 더한 자료구조는 없을 것입니다.

최초의 C에 들어 있는 물의 양은 A와 B에는 0이 들어 있으므로 0을 두 번 삽입합니다.

이로 인해 visit[0][0]은 true, ans[arr[2]]도 true로 바꾸어주어야 하는데 이는 A와 B가 0일 때에는 C는 오직 하나의 값만 가지는 유일성을 보장해주기 위함이며 ans가 true일 때에는 C의 값이 arr[2]라는 값을 가지는 것을 의미합니다.

이후 while문을 이용합니다.

while (!queue.isEmpty()) {
    int[] temp = new int[3];
    temp[0] = queue.remove();
    temp[1] = queue.remove();
    temp[2] = sum - temp[0] - temp[1];
    for(int k = 0; k < 6; k++){
        int[] next = {temp[0], temp[1], temp[2]};
        next[dir[k][0]] += next[dir[k][1]];
        next[dir[k][1]] = 0;
        if(next[dir[k][0]] >= arr[dir[k][0]]){
            next[dir[k][1]] = next[dir[k][0]] - arr[dir[k][0]];
            next[dir[k][0]] = arr[dir[k][0]];
        }
        if(!visit[next[0]][next[1]]){
            visit[next[0]][next[1]] = true;
            queue.offer(next[0]);
            queue.offer(next[1]);
            if(next[0] == 0){
                ans[next[2]] = true;
            }
        }
    }
}

여기서 정신 빠짝 차리고 따라오셔야 합니다.

저는 임시 배열로 temp라는 3의 크기의 배열을 선언할 것입니다.

또한 temp[0]은 queue에서 최초로 꺼낸 것이고 temp[1]은 queue에서 그 다음에 꺼낸 값을 담습니다.

temp[2]는 sum에서 temp[0]과 temp[1]을 뺀 값이라고 해봅시다.

그럼 총 6가지 경우의 수에 대해 물을 옮길 수 있는데 저는 for문을 사용하여 구현해보겠습니다.

int[] next = {temp[0], temp[1], temp[2]};
next[dir[k][0]] += next[dir[k][1]];
next[dir[k][1]] = 0;
if(next[dir[k][0]] >= arr[dir[k][0]]){
    next[dir[k][1]] = next[dir[k][0]] - arr[dir[k][0]];
    next[dir[k][0]] = arr[dir[k][0]];
}

제가 BFS문제를 주로 풀 때 인덱스 방향이 새로 지정되면 nx와 ny를 썼던 것을 기억하시나요?

nextX와 nextY를 줄여서 써서 그런 것인데 저는 여기서 next라는 배열로 새로 이동할 인덱스 배열을 지정하겠습니다.

이 next배열에는 temp[0]과 temp[1], temp[2]를 차례로 삽입합니다.

저희는 BFS문제를 풀고 있습니다.

따라서 각각의 next배열에 대해 총 6가지 경우의 이동가지 수를 계산하여야 합니다.

때문에 next[dir[k][0]]에는 next[dir[k][1]]을 더하고 next[dir[k][1]]은 으로 바꾸어줄텐데요.

이는 각각의 6가지 경우의 수에 대해 1에서 0으로, 1에서 2로, 2에서 1로, 2에서 0으로, 0에서 1로, 0에서 2로 갈 수 있는 경우를 k로 표현한 것입니다.

(직접 k에 값을 넣어보며 위의 dir값과 비교해보세요.)

그리고 여기서 마치지 않고 next[dir[k][0]]의 값이 arr의 dir[k][0]의 값보다 커진다면 next[dir[k][1]]의 값을 arr[dir[k][0]]값만큼만 덜어서 넣습니다.

그리고 남은 양은 next[dir[k][1]]에 넣을텐데요.

이것은, 물을 넣을 때 용량을 초과하게 되면 다시 그 차이만큼 원래의 물통에 넣음을 의미합니다.

그리고

if(!visit[next[0]][next[1]]){
    visit[next[0]][next[1]] = true;
    queue.offer(next[0]);
    queue.offer(next[1]);
    if(next[0] == 0){
        ans[next[2]] = true;
    }
}

이 부분이 가장 어려운데 잘 따라오셔야 합니다.

저는 만약 visit[next[0]][next[1]]의 값이 false이면 다음과 같은 로직을 진행하도록 짰습니다.

이게 뭘 의미하냐면, visit[next[0]][next[1]]의 값은 여러 번 반복될 경우 C의 값은 항상 일정하게 나오는데 중복되어 탐색할 수 있습니다.

이를 피하기 위한 로직이라고 생각하시면 되겠습니다.

예를 들어 0 0 9(용량 : 7 8 9)라고 한다면 0 0 9가 여러 번 계속 실행된다고 생각해보십시오.

불필요한 로직 탐색을 줄여야 알고리즘의 완성도가 올라가게 되므로 이는 BFS과정에서 필수적인 조건입니다.

그리고 이것에 그치지 않고 ans의 배열도 신경을 써주셔야하는데요.

로직을 자세히 보시면, 일단 visit[next[0]][next[1]]을 true로 바꾼 뒤에 queue에 2개를 모두 삽입하는 것을 아실 수 있습니다.

이는 새로운 A와 B를 구했다는 것을 의미한다 이해하면 되시고요.

이 때 만약 next[0]이 0이라면 (A가 0이라면) 이 때의 next[2]는 C의 상태이며 ans[next[2]]를 true로 바꾸어 줍니다.

물론 false일 경우 true로 바꾸어 주어도 되지만 시간 복잡도는 동일하게 나올 것으로 예상이 되므로 그냥 true를 계속 삽입하겠습니다.

그리고 더 이상 queue에 담긴 값이 없으면 알아서 while문이 종료되어 밖으로 나오게 됩니다.

이후 ans[i]가 true인 값에 대해서만 출력하시면 정답이 되겠습니다.

감사합니다.