[백준 JAVA] 14466 : 소가 길을 건너간 이유 6

[백준 14466] 소가 길을 건너간 이유 6 : https://www.acmicpc.net/problem/14466

---

문제 조건 정리

 

1. 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다.
2. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. -> 사실상 (길 == 벽)
3. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. -> 테두리 검사해야함
4. K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다.
5. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자. -> 쌍 공식 -> K*(K-1)/2

---

입력

 

1. 첫 줄에 N, K, R이 주어진다.
   
   
2. 다음 R줄에는 한 줄에 하나씩 길이 주어진다.
   길은 상하좌우로 인접한 두 목초지를 잇고, -> "인접" 이라는 키워드 : abs(r - r') + abs(c-c') == 1,
   r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다.
   각 수는 1 이상 N 이하이다.
   
   
3. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

---

문제를 풀면서

 

1. 길, 사실상 문제의 벽을 어떻게 표현할지에 대해서, 상당한 수정을 거치면서 문제를 풀었음. 효율적으로 해결하기 위해서.
   boolean[][] 으로 길을 표현
   -> 상하좌우를 따질 수 없음
   
   boolean[][] 으로 길을 표현, List<>에 길의 출발 지점과 도착 지점을 짝지음
   -> 비효율적.. 출발 지점의 인덱스를 알 수 없으니, 탐색을 통해서 찾아야함
   
   int[][] 으로 길을 표현
   -> 상하좌우 값을 어떻게 설정해야할지 모르겠음, 리스트를 붙여도 비효율적
   
   Map<int[], int[]> 으로 길을 표현
   -> int[]은 객체로서 값의 주소로 표현됨, 값이 같아도 키로서 역할을 못함
   
   List<List<Integer>> 으로 길을 표현
   -> 비효율적, 탐색이 필요함
   
   이외에도 문자열로 표현을 하는 등, 여러 방법을 생각하거나 시도해봤으나 맘에 들지 않았다.
   그때 머리속을 스치는 생각, 비트마스킹!
   이전에 풀었던 백준의 성곽 문제(https://www.acmicpc.net/problem/2234)가 생각났다.
   
   성곽 문제에서는 진작에 입력으로 비트마스킹하게 사용하라고 힌트를 줬었다.
   (벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.)
   
   알고 보면 간단한데 이를 위해서 얼마나 고생했나..
   본 문제에서도 길을 벽으로 생각하고, 상하좌우를 1, 2, 4, 8의 값으로 int[][]에 저장하는게 맞았고, 그걸 유도했다고 생각한다.
   성곽 문제와 다르게 힌트는 없었지만.
   
   
2. 위 내용의 구현은 헷갈릴 수 있지만 간단했다.
   헷갈릴 수 있는 내용은 현재 내 위치를 기준으로 아래로 길(벽)이 있다면, 내 위치의 아래에서는 위에 길(벽)이 있다고 표시해야한다는 점이다. 그래프에서 인접 리스트를 구현할 때와 동일하다고 할 수 있다.
   
   
3. 비트마스킹은 +=으로 하기보다 |=으로 하는게 당연히 더 좋다.
   자세한 내용은 아래 코드에서 확인할 수 있다.
   
   
4. 마지막으로 길을 건너지 않으면 만날 수 없는 소의 쌍은 전체 쌍을 구하고 만날 수 있는 쌍의 수를 뺐다.
   k*k-1/2를 활용했다. 자세한 설명은 키워드(조합, 이항계수)를 검색해보면 된다!
   
    

---

코드

 

package baekJoon;

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

public class BJ14466 {

    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1}; // 상, 하, 좌, 우
    static int n;
    static int[][] roadInfo;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

        n = Integer.parseInt(stringTokenizer.nextToken());
        int k = Integer.parseInt(stringTokenizer.nextToken());
        int r = Integer.parseInt(stringTokenizer.nextToken());

        roadInfo = new int[n + 1][n + 1];
        int[][] cowChecker = new int[n + 1][n + 1];

        for (int i = 0; i < r; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            int sr = Integer.parseInt(stringTokenizer.nextToken());
            int sc = Integer.parseInt(stringTokenizer.nextToken());
            int er = Integer.parseInt(stringTokenizer.nextToken());
            int ec = Integer.parseInt(stringTokenizer.nextToken());

            if (sr == er) {
                if (sc < ec) { // 오른쪽
                    roadInfo[sr][sc] |= 8; // 오른쪽 방향
                    roadInfo[er][ec] |= 4; // 왼쪽 방향
                } else { // 왼쪽
                    roadInfo[sr][sc] |= 4; // 왼쪽 방향
                    roadInfo[er][ec] |= 8; // 오른쪽 방향
                }
            } else if (sc == ec) {
                if (sr < er) { // 아래쪽
                    roadInfo[sr][sc] |= 2; // 아래쪽 방향
                    roadInfo[er][ec] |= 1; // 위쪽 방향
                } else { // 위쪽
                    roadInfo[sr][sc] |= 1; // 위쪽 방향
                    roadInfo[er][ec] |= 2; // 아래쪽 방향
                }
            }
        }

        for (int i = 0; i < k; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            int row = Integer.parseInt(stringTokenizer.nextToken());
            int col = Integer.parseInt(stringTokenizer.nextToken());
            cowChecker[row][col] = i + 1;
        }

        boolean[][] visited = new boolean[n + 1][n + 1];
        List<List<Integer>> cowsIdxList = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (visited[i][j]) continue;
                List<Integer> cowsIdx = new ArrayList<>();

                Queue<int[]> queue = new ArrayDeque<>();
                queue.offer(new int[]{i, j});
                visited[i][j] = true;

                while (!queue.isEmpty()) {
                    int[] curr = queue.poll();

                    if (cowChecker[curr[0]][curr[1]] != 0) {
                        cowsIdx.add(cowChecker[curr[0]][curr[1]]);
                    }

                    for (int d = 0; d < 4; d++) {
                        int nx = curr[0] + dx[d];
                        int ny = curr[1] + dy[d];

                        if (!isSafe(nx, ny)) continue;
                        if (visited[nx][ny]) continue;
                        if ((roadInfo[curr[0]][curr[1]] & (1 << d)) != 0) continue; // 이동 불가능한 방향 체크

                        queue.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }

                if (!cowsIdx.isEmpty()) {
                    cowsIdxList.add(cowsIdx);
                }
            }
        }

//        for (List<Integer> ci : cowsIdxList) {
//            for (int i : ci) {
//                System.out.print(i + " ");
//            }
//            System.out.println();
//        }

        // 각 구역의 소 수
        List<Integer> groupSizes = new ArrayList<>();
        for (List<Integer> ci : cowsIdxList) {
            groupSizes.add(ci.size());
        }

        // 전체 쌍의 수
        int totalPairs = (k * (k - 1)) / 2;

        // 같은 구역 내 쌍의 수
        int sameGroupPairs = 0;
        for (int size : groupSizes) {
            if (size > 1) {
                sameGroupPairs += (size * (size - 1)) / 2;
            }
        }

        // 구역이 다른 소들 간의 쌍의 수
        int differentGroupPairs = totalPairs - sameGroupPairs;

        System.out.println(differentGroupPairs);
    }

    private static boolean isSafe(int nx, int ny) {
        return 1 <= nx && nx <= n && 1 <= ny && ny <= n;
    }
}

// 2 3
// 1 4
// 5 6

 

---

문제를 풀고 난 후

 

고민을 통해서 올바른 문제 해결 방법을 떠올릴 수 있어서 행복했다.
BFS를 많이 풀어봤는데 비트마스킹 기법을 사용한 경험이 많지 않았다.

최근에 성곽 문제를 풀면서 비트연산자를 조금 공부한 덕분에 코드를 깔끔하게 작성할 수 있었다.