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

 

문제 링크 : www.acmicpc.net/problem/14466

14466번: 소가 길을 건너간 이유 6

풀이

소의 위치를 시작점으로 하여 BFS를 통해 목초지를 탐색하되, 다리가 존재하는 경우는 탐색하지 않도록한다.

탐색이 끝나고 다른 소 위치에 대한 방문 여부를 체크하는데

이 때 방문이 되지 않은 경우는 다리를 지나지 않으면 만날 수 없다는 것을 의미하기 때문에 해당 경우를 모두 찾으면 된다.

 

2차원 int 배열 map은 BFS탐색을 할 목초지로 소 위치는 1로 두고 나머지는 0으로 둔다.

다리의 여부는 bridges라는 이름의 2차원 ArrayList배열에 저장을 한다.

 

BFS 탐색 시 방문 가능여부를 체크할 때 다리가 있는 경우,

즉 현재 위치에 해당하는 bridges 리스트에 다음 위치 노드가 포함되어 있는 경우는 탐색을 하지 않는다.

주의할 점은 contains()를 사용했는데 이 함수 내부에서는 equals()함수를 사용한다.

equals()는 객체의 저장 주소를 기반으로 탐색하기 때문에

Node 객체의 equals() 함수를 재정의하여 x,y를 기반으로 동일한 객체 여부를 체크하도록 해야한다.

 

탐색 중, 해당 노드가 1인 경우(소가 있는 위치인 경우) 소 위치를 저장해둔 cows 리스트에서 해당 소의 index를 찾아 내고,

소끼리 접촉 여부를 저장하는 cowContacted 배열에, 두 소의 index를 true로 변경한다.

 

BFS 탐색이 종료되면, cows 리스트를 탐색하여

true가 아닌 경우(소가 만나지 않은 경우 == 다리가 없으면 못 만나는 경우)를 찾아 그 갯수를 카운팅하면 된다.

이 때, 1쌍을 찾는 것이기 때문에 1번째 소가 2번째 소를 만난 것 == 2번째 소가 1번째 소를 만난 것이 되어야한다.

이러한 중복을 제거하기 위해서는 BFS 탐색을 시작했던 소의 인덱스가 i라면 i번 째 이후의 소들의 위치만 찾아야한다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int N;
    private static int[] x_move = {1, 0, -1, 0};
    private static int[] y_move = {0, 1, 0, -1};

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

        N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());

        int[][] map = new int[N + 1][N +1];

        ArrayList<Node>[][] bridges = new ArrayList[N + 1][N + 1];

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                bridges[i][j] = new ArrayList<>();
            }
        }

        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());

            int r1 = Integer.parseInt(st.nextToken());
            int c1 = Integer.parseInt(st.nextToken());
            int r2 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());

            bridges[r1][c1].add(new Node(r2, c2));
            bridges[r2][c2].add(new Node(r1, c1));
        }

        List<Node> cows = new ArrayList<>();
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            cows.add(new Node(x, y));
            map[x][y] = 1;
        }

        int answer = 0;

        for (int t = 0; t < K; t++) {
            Node cow = cows.get(t);

            int count = 0;

            boolean[][] visited = new boolean[N + 1][N + 1];
            boolean[][] cowContacted = new boolean[K][K];
            Queue<Node> queue = new LinkedList<>();

            queue.offer(cow);
            visited[cow.x][cow.y] = true;

            while (!queue.isEmpty()) {
                Node node = queue.poll();

                if (map[node.x][node.y] == 1) {
                    for (int j = t + 1; j < K; j++) {
                        Node nextCow = cows.get(j);

                        if (nextCow.x == node.x && nextCow.y == node.y) {
                            cowContacted[t][j] = true;
                            break;
                        }
                    }
                }

                for (int i = 0; i < 4; i++) {
                    int new_x = node.x + x_move[i];
                    int new_y = node.y + y_move[i];

                    if (!isInArea(new_x, new_y) || visited[new_x][new_y]) {
                        continue;
                    }

                    if (bridges[node.x][node.y].contains(new Node(new_x, new_y))) {
                        continue;
                    }

                    visited[new_x][new_y] = true;
                    queue.offer(new Node(new_x, new_y));
                }
            }

            for (int i = t + 1; i < K; i++) {
                if (!cowContacted[t][i]) {
                    answer++;
                }
            }
        }

        System.out.println(answer);
    }

    private static boolean isInArea(int x, int y) {
        return x > 0 && y > 0 && x <= N && y <= N;
    }

    static class Node {
        private int x;
        private int y;

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

        @Override
        public boolean equals(Object obj) {
            Node node = (Node) obj;

            return this.x == node.x && this.y == node.y;
        }
    }
}