[백준] 14466번. 소가 길을 건너간 이유 6(JAVA)

문제

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

---

풀이

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

public class Main {

    static int N, K, R;
    static Map<Point, List<Point>> bridge = new HashMap<>();
    static ArrayList<Point> cowPoint = new ArrayList<>();

    static boolean[][] cow;
    static boolean[][] visited;
    static int count;
    static Queue<Point> queue = new LinkedList<>();
    static int totalCowPairs = 0;  // 모든 소 쌍의 수
    static int connectedPairs = 0; // 서로 연결된 소 쌍의 수

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        cow = new boolean[N][N];
        visited = new boolean[N][N];

        // Bridge 정보 입력
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            Point startPoint = new Point(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
            Point endPoint = new Point(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);

            bridge.computeIfAbsent(startPoint, k -> new ArrayList<>()).add(endPoint);
            bridge.computeIfAbsent(endPoint, k -> new ArrayList<>()).add(startPoint);
        }

        // 소의 위치 입력
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            cow[x][y] = true;
            cowPoint.add(new Point(x, y));
        }

        // 모든 소 쌍의 수는 K * (K - 1) / 2
        totalCowPairs = K * (K - 1) / 2;

        // 각 소에서 다른 소까지 BFS 탐색
        for (int i = 0; i < cowPoint.size(); i++) {
            visited = new boolean[N][N];
            queue.add(cowPoint.get(i));
            visited[cowPoint.get(i).x][cowPoint.get(i).y] = true;
            bfs();
        }

        // 소가 연결되지 않은 쌍의 수는 totalCowPairs - connectedPairs
        int answer = (K*(K-1)/2) - (totalCowPairs - connectedPairs);
        System.out.println(answer);
    }

    // BFS로 소들 간의 연결 상태 탐색
    public static void bfs() {
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int x = point.x;
            int y = point.y;

            // 현재 위치에서 상하좌우로 이동하며 탐색
            explore(x - 1, y, point);
            explore(x + 1, y, point);
            explore(x, y - 1, point);
            explore(x, y + 1, point);
        }
    }

    // 새로운 좌표로 이동 가능한지 확인 후 탐색
    public static void explore(int newX, int newY, Point currentPoint) {
        if (newX >= 0 && newX < N && newY >= 0 && newY < N && !visited[newX][newY]) {
            Point newPoint = new Point(newX, newY);

            // 현재 위치에서 새 위치로 가는 다리가 없다면 이동 가능
            List<Point> connectedPoints = bridge.getOrDefault(currentPoint, new ArrayList<>());

            // 다리가 연결되지 않았으면 이동 가능
            if (!connectedPoints.contains(newPoint)) {
                visited[newX][newY] = true;
                queue.add(newPoint);

                // 새로운 위치에 소가 있는지 확인
                if (cow[newX][newY]) {
                    // 소들이 연결된 경우 카운트
                    connectedPairs++;
                }
            }
        }
    }

    // Point 클래스 equals, hashCode 메서드 재정의
    static class Point {
        int x, y;

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

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}

 

Point라는 점을 먼저 정의했다. 이 점은 equals, hashCode를 오버라이딩 함으로써 값이 같다면 같은 객체로 인식할 수 있게 해두었다.(이렇게 하지 않는다면 소의 위치 점과, 다리의 위치 점의 객체 주소 비교로 인해 동일하게 인식하지 못한다.)

 

이후 아이디어는 간단한다. 다리의 경우 양쪽 모두 해당하는 조건이므로 다리를 추가할 때 양쪽을 모두 넣어준다.

 

최종적으로 bfs를 진행하며 소 한마리당 만날 수 있는 소를 찾아간다. 이후, 이 것을 절반으로 나눈 뒤 총 소 쌍에서 빼줌으로써 정답을 구한다.

 

별 다른 아이디어는 없지만 오버라이딩 등 코딩적으로 좀 귀찮았던 문제같다. 또한, 점을 Map<Point, List<Point>>로 관리하여 하나의 점에 대해 여러가지 점을 보관하는 방법을 사용한 것 정도가 어려웠던 것 같다.

 

마지막으로, 고등학교 수학시간에도 많이 나왔던 여집합을 구하는 것이 문제의 엄청난 아이디어가 될 수 있음을 항상 주목하자.