[Boj_14466] 소가 길을 건너간 이유 6

📎 문제 링크

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

 

▸ 문제

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

 

▸ 입력

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

 

▸ 출력

길을 건너지 않으면 만날 수 없는 소가 몇 쌍인지 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 3
• 🔔  문제 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 소의 위치와 다리(길)의 위치가 주어졌을 때, 다리를 건너야 하는 소가 몇 쌍인지 구하는 문제이다.

 

문제 이해를 위해 예제 입력 1을 예시로 들어보자

먼저 소와 다리가 위와 같이 위치한다.

빨간색 소와 파란색 소는 다리를 이용하지 않고 만날 수 있다.

하지만 빨간색 소와 초록색 소가 만나기 위해서는 무조건 다리를 이용해야 한다.

마찬가지로 파란색 소와 초록색 소가 만나기 위해서는 무조건 다리를 이용해야 한다.

 

이렇게 되면 다리를 건너야 하는 소는 두 쌍이다.

 

너비 우선 탐색을 사용하여 다리를 건너지 않고 도달할 수 없는 쌍을 구하는 방식으로 문제를 해결할 수 있다.

다리에 대한 정보를 저장하고 해당 좌표로 이동할 때, 다리가 있다면 더 이상 탐색을 이어가지 않도록 한다.

또한, 쌍을 구하는 것이므로 자신보다 앞에 있는 소들은 계산할 필요가 없다.

 

위 풀이대로 코드를 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 32584KB
시간 : 300ms

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

public class Main {
    static int n, k, r;
    static int[][] cow;
    static boolean[][] checked;
    static ArrayList<Pos>[][] road;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static public class Pos {
        int x; int y;
        public Pos (int x, int y) {
            this.x = x; this.y = y;
        }
    }
    static int ans;
    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()); // n*n
        k = Integer.parseInt(st.nextToken()); // 소의 수
        r = Integer.parseInt(st.nextToken()); // 다리(길)의 위치 정보

        road = new ArrayList[n][n]; // 다리에 대한 정보 저장
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                road[i][j] = new ArrayList<>();
            }
        }
        int a, b, c, d;
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken())-1;
            b = Integer.parseInt(st.nextToken())-1;
            c = Integer.parseInt(st.nextToken())-1;
            d = Integer.parseInt(st.nextToken())-1;

            road[a][b].add(new Pos(c, d));
            road[c][d].add(new Pos(a, b));
        }
        
        cow = new int[k][2]; // 소가 있는 위치
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken())-1;
            b = Integer.parseInt(st.nextToken())-1;
            
            cow[i][0] = a;
            cow[i][1] = b;
        }

        // 결과적으로 쌍을 구하는 것이기 때문에 자기보다 뒤에 있는 소들만 계산하면 된다.
        for (int i = 0; i < k; i++) {
            bfs(cow[i][0], cow[i][1], i);
        }

        // 길을 건너지 않으면 만날 수 없는 소가 몇 쌍 ?
        System.out.println(ans);
    }

    private static void bfs(int x, int y, int idx) {
        Queue<Pos> que = new LinkedList<>();
        que.offer(new Pos(x, y));

        checked = new boolean[n][n];
        checked[x][y] = true;

        while (!que.isEmpty()) {
            Pos now = que.poll();

            for (int d = 0; d < 4; d++) {
                int nx = dx[d] + now.x;
                int ny = dy[d] + now.y;

                if (rangeCheck(nx, ny)) continue;

                boolean flag = false; // 다리가 있는지 체크
                for (int i = 0; i < road[now.x][now.y].size(); i++) {
                    Pos tmp = road[now.x][now.y].get(i); // 다리 정보

                    if (nx == tmp.x && ny == tmp.y) {
                        flag = true;
                        break;
                    }
                }

                // 다리가 있다면 탐색 X
                if (flag || checked[nx][ny]) continue;

                checked[nx][ny] = true;
                que.offer(new Pos(nx, ny));
            }
        }

        for (int i = idx; i < k; i++) {
            if (!checked[cow[i][0]][cow[i][1]]) ans++;
        }
    }

    private static boolean rangeCheck(int x, int y) {
        return x < 0 || x >= n || y < 0 || y >= n;
    }
}

 

해결 완료 ! 🔥