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

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

 

풀이 방법

먼저 문제를 이해하는 것이 중요하다.

농장에서 다리가 없는 곳은 자유롭게 이동이 가능하지만, 다리가 연결된 곳은 다리를 건너야 이동이 가능하다.

주어진 예시를 통해 이해해 보자

위 이미지에서 체크가 소의 위치 사각형의 변에 동그라미가 다리의 위치이면, (3,3)의 위치로 이동하기 위해선 무조건 다리를 건너야 한다.

하지만, (2, 2)와 (2, 3)은 다리를 이용하지 않고 돌아서 (2, 2), (1, 2), (1, 3), (2, 3)와 같이 다리를 이용하지 않고 이동이 가능하다.

 

이 문제를 쉽게 구현하기 위해, 다리를 저장하는 자료구조가 중요했다.

다리라는 3차원 배열을 선언한 뒤 bridge [y][x][dir] 해당 배열을 y, x에서 dir방향 쪽으로의 다리가 존재하느냐로 설정했다.

그 후 bfs를 돌며 다리가 존재한다면 cotinue를 통해 탐색하지 않았다.

해당 방법으로 구역을 정한 후, 각 구역에 위치한 소의 수를 구해서, 조합을 계산할 수 있었다.

 

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

public class P_14466 {
    static int n, k, r;
    static int[][] visited = new int[101][101];
    static int[][][] bridge = new int[101][101][4];
    static int[] dy = {0, 0, -1, 1};
    static int[] dx = {1, -1, 0, 0}; // 우, 좌, 상, 하
    static ArrayList<ArrayList<Integer>> cowNum = new ArrayList<>();

    static void checkBridge(int a, int b, int c, int d) { // 다리 만들기
        if (a > c) {
            bridge[a][b][2] = 1;
            bridge[c][d][3] = 1;
        }
        else if (a < c) {
            bridge[a][b][3] = 1;
            bridge[c][d][2] = 1;
        }
        else if (b > d) {
            bridge[a][b][1] = 1;
            bridge[c][d][0] = 1;
        }
        else if (b < d) {
            bridge[a][b][0] = 1;
            bridge[c][d][1] = 1;
        }
    }
    static void bfs(int y, int x, int cnt) { // 구역 나누기
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{y, x});

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int yy = cur[0];
            int xx = cur[1];
            for (int i = 0; i < 4; i++) {
                int ny = yy + dy[i];
                int nx = xx + dx[i];
                if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue; // 범위를 벗어난 경우
                if (visited[ny][nx] != 0) continue; // 이미 방문한 경우
                if (bridge[yy][xx][i] == 1) continue; // 다리를 건너야 하는 경우
                q.add(new int[]{ny, nx});
                visited[ny][nx] = cnt;
            }
        }
    }
    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());
        k = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        int a, b, c, d;
        for (int i = 0;i < r;i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            checkBridge(a-1, b-1, c-1, d-1);
        }
        int cnt = 1;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                if (visited[i][j] == 0) {
                    visited[i][j] = cnt;
                    bfs(i, j, cnt);
                    cnt++;
                }
            }
        }
        for (int i = 0;i <= cnt;i++) {
            cowNum.add(new ArrayList<>());
        }
        for (int i = 0;i < k;i++) { // 각 구역의 소의 수를 계산
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            cowNum.get(visited[a-1][b-1]).add(i);
        }
        int ans = 0;
        for (int i = 1;i <= cnt;i++) { // 조합 계산하기 
            for (int j = i+1;j <= cnt;j++) {
                ans += cowNum.get(j).size() * cowNum.get(i).size();
            }
        }
        System.out.println(ans);
    }
}