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

소가 길을 건너간 이유 6

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	704	315	237	44.802%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

xxxxxxxxxx
3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3

예제 출력 1 복사

2

 

 

 

풀이

bfs로 풀었습니다.

 

인접리스트로 길으로 가야하는 곳을 담아 두었고

bfs에서는 현재 좌표에서 길이 아닌곳만 탐색하도록 했습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int n,k,r;
    static ArrayList<Node>info[][];
    static int arr[][];
    static boolean visited[][];
    static int dx [] = {0,0,1,-1};
    static int dy [] = {1,-1,0,0};
    static int ans = 0;
    static int map[][];
​
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        String [] t = br.readLine().split(" ");
        
        n = Integer.parseInt(t[0]);
        k = Integer.parseInt(t[1]);
        r = Integer.parseInt(t[2]);
        
        info = new ArrayList[n+1][n+1];     // 길 정보
        map = new int[n+1][n+1];        // 소가 있는 위치정보
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                info[i][j] = new ArrayList<>();
            }
        }
        
        for(int i=0; i<r; i++) {
            t = br.readLine().split(" ");
            int x1 = Integer.parseInt(t[0]);
            int y1 = Integer.parseInt(t[1]);
            int x2 = Integer.parseInt(t[2]);
            int y2 = Integer.parseInt(t[3]);
            
            info[x1][y1].add(new Node(x2,y2));
            info[x2][y2].add(new Node(x1,y1));
        }
        
        
        for(int i=0; i<k; i++) {
            t = br.readLine().split(" ");
            int x = Integer.parseInt(t[0]);
            int y = Integer.parseInt(t[1]);
            map[x][y] = 1;
        }
        
​
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(map[i][j]==1) {
                    bfs(i,j);
                }
            }
        }
        System.out.println(ans/2);
    }
    public static void bfs(int x, int y) {
        visited = new boolean [n+1][n+1];
        Queue<Node>q = new LinkedList<>();
        int cnt = -1;
        q.add(new Node(x,y));
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            Node a = q.poll();
            if( map[a.x][a.y]==1) {
                cnt++;
            }
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                boolean flag = true;
                if(isRange(nx,ny) && !visited[nx][ny]) {
                    for(Node tmp : info[a.x][a.y]) {
                        if(tmp.x == nx && tmp.y== ny) {
                            flag= false;
                            continue;
                        }
                    }
                    
                    if(flag) {
                        
                        q.add(new Node(nx,ny));
                        visited[nx][ny]= true;
                    }
                }
            }
        }
        ans += (k-cnt-1);
    }
    public static boolean isRange(int x, int y) {
        if(x>=1 && y>=1 && x<=n && y<=n) {
            return true;
        }
        return false;
    }
}
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}
​