[BOJ] 14867번 물통 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static int a, b;
    static Set<String> usedSet;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        int targetA = Integer.parseInt(st.nextToken());
        int targetB = Integer.parseInt(st.nextToken());
        usedSet = new HashSet<String>();

        System.out.println(bfs(targetA, targetB));
    }

    static int bfs(int targetA, int targetB) {
        Queue<Status> q = new LinkedList<Status>();
        q.offer(new Status(0, 0));

        while (!q.isEmpty()) {
            Status now = q.poll();
            int x = now.x;
            int y = now.y;
            int cnt = now.count;
            
            if (x == targetA && y == targetB) {
                return cnt;
            }

            for (int i = 1; i <= 6; i++) {
                // 다음 x, y 초기화 (이 부분 놓치고 틀렸음)
                int nx = x;
                int ny = y;

                if (!isValid(i, nx, ny)) continue;

                switch (i) {
                    case 1:
                        nx = a;
                        break;
                    case 2:
                        ny = b;
                        break;
                    case 3:
                        nx = 0;
                        break;
                    case 4:
                        ny = 0;
                        break;
                    case 5:
                        if (b - ny < nx) {
                            nx = nx - (b - ny);
                            ny = b;
                        } else {
                            ny += nx;
                            nx = 0;
                        }
                        break;
                    case 6:
                        if (a - nx < ny) {
                            ny = ny - (a - nx);
                            nx = a;

                        } else {
                            nx += ny;
                            ny = 0;
                        }
                        break;
                }

                if (isUsed(nx, ny)) {
                    continue;
                }
                q.offer(new Status(nx, ny, cnt + 1));
            }
        }

        return -1;
    }

    private static boolean isValid(int i, int nx, int ny) {
        // 차있는 경우 채우기 수행하지 않음
        if (nx == a && i == 1) {
            return false;
        }
        if (ny == b && i == 2) {
            return false;
        }

        // 비어있는 경우 이동이나 비우기 수행하지 않음
        if (nx == 0) {
            if (i == 3 || i == 5) {
                return false;
            }
        }
        if (ny == 0) {
            if (i == 4 || i == 6) {
                return false;
            }
        }
        return true;
    }

    static boolean isUsed(int x, int y) {
        String point = x + "_" + y;
        if (usedSet.contains(point)) {
            return true;
        }

        usedSet.add(point);
        return false;
    }

    static class Status {
        int x;
        int y;
        int count = 0;

        Status(int x, int y) {
            this.x = x;
            this.y = y;
        }

        Status(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}

📄 해설

접근

• BFS 알고리즘을 이용하여 푸는 문제. 2개의 물통에 대해 3개의 작업을 모두 탐색해보면 된다.
• 100,000 X 100,000 크기의 방문 배열을 사용할 수 없으므로, HashSet 을 사용해야한다.
• 이렇게까지 접근했다면 나머지는 조건 분기여서 크게 어려움은 없다.
• BFS while 루프의 내부 루프마다 물의 양을 초기화해주어야한다. (놓쳐서 틀린 부분)

과정

• 큐에서 물통에 담긴 물과 작업 횟수를 담은 노드를 꺼낸다.
• 목표한 상태인지 확인하고, 목표한 상태이면 현재까지의 작업 횟수를 반환한다.
• 2개의 물통에 대해 3개의 작업을 확인해야하므로, 6번의 반복문을 수행한다.
  • 매 반복마다 현재 물통의 양으로 초기화를 해줘야함 (이 부분을 놓치고 코드를 작성하면 -1 만 출력됨)
  • isValid 메소드를 통해 가지치기를 수행해준다. (불필요한 작업 무시)
  • 각 작업에 맞게 작업을 수행한다.
  • 다음 상태가 방문되었는지를 확인하고, 방문하지 않았으면 큐에 넣고 위 과정을 반복한다.