백준 14466번 소가 길을 건너간 이유6(자바) - bfs/ 2차원 ArrayList

소가 길을 건너간 이유 6 성공

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

2340

955

716

39.602%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3

예제 출력 1 복사

2

---

처음에는 문제가 이해가 안 갔는데 

백준 14466 <소가 길을 건너간 이유 6> (tistory.com)

백준 14466 <소가 길을 건너간 이유 6>

이 블로그를 보고 문제를 이해했다.

즉, 한 소의 위치에서 bfs를 통해 길이 없는 곳만을 돌아다니면서 visited를 체크하고 que에 넣는다.

그 후 자신보다 인덱스 값이 큰 소들의 위치에 대해 그 위치의 visited = false라면 길이 없으면 만나지 못하는 소이므로 answer++을 해준다. 

이 과정을 모든 소에 대해 반복한다.

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Node {
    int x;
    int y;
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int[][] cow;
    static int n,k,r;
    static boolean[][] visited;
    static ArrayList<Node>[][] road;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int answer = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        r = sc.nextInt();
        cow = new int[k][2];
        road = new ArrayList[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                road[i][j] = new ArrayList<>();
            }
        }
        visited = new boolean[n][n];
        for (int i = 0; i < r; i++) {
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            int c = sc.nextInt()-1;
            int d = sc.nextInt()-1;
            road[a][b].add(new Node(c,d));
            road[c][d].add(new Node(a,b));
        }
        for (int i = 0; i < k; i++) {
            cow[i][0] = sc.nextInt()-1;
            cow[i][1] = sc.nextInt()-1;
        }
        for (int i = 0; i < k; i++) {
            bfs(cow[i][0], cow[i][1], i);
        }
        System.out.println(answer);
    }

    static void bfs(int x, int y, int idx) {
        visited = new boolean[n][n];
        Queue<Node> que = new LinkedList<>();
        que.offer(new Node(x, y));
        visited[x][y] = true;
        while (!que.isEmpty()) {
            Node now = que.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                boolean flag = false;
                for (int j = 0; j < road[now.x][now.y].size(); j++) {
                    Node tmp = road[now.x][now.y].get(j);
                    if (nx == tmp.x && ny == tmp.y) {
                        flag = true;
                        break;
                    }
                }
                if (flag || visited[nx][ny]) continue;
                visited[nx][ny] = true;
                que.offer(new Node(nx, ny));
            }
        }
        for (int i = idx; i < cow.length; i++) {
            if (!visited[cow[i][0]][cow[i][1]]) answer++;
        }
    }
}