[BOJ] 14466번: 소가 길을 건너간 이유 6 (JAVA)

문제 (Gold 4)

14466번: 소가 길을 건너간 이유 6

풀이

문제 해석

1. 일반 목초지 사이는 상하좌우 모두 움직일 수 있다.

2. 중간에 다리가 있다면, 다리를 꼭 건너야 한다.

즉, 소(2,2)는 소(2,3)까지 다리를 건너야할 수도 있지만, 그 길을 회피해 회색 화살표 길로 갈 수 있다.

소(3,3)은 다른 목초지에 가려면 무조건 다리를 건너야 하므로, 모든 소와 유효한 쌍이 된다.

풀이

1. 소가 있는 곳을 중심으로 BFS 탐색을 하여, 영역을 표시한다.

2. 모든 소가 있는 곳의 영역을 탐색

3. 현재 소와 그 다음 소들을 비교하며 다른 영역에 있다면 결과값을 +1 한다.

코드

더보기

package graphTraversal;

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

public class BOJ_14466_소가길을건너간이유6 {
    static int[] di = {-1, 0, 1, 0};
    static int[] dj = {0, -1, 0, 1};
    static int N,K,R;
    static List<int[]> bridge;  // 다리의 정보를 저장
    static List<int[]> cowPos;  // 소의 위치의 정보를 저장
    static int[][] map; // 영역을 저장
    public static void main(String[] args) throws Exception{
        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());
        bridge = new ArrayList<>();
        cowPos = new ArrayList<>();
        map = new int[N][N];
        for(int i =0 ; i < N ; i++) Arrays.fill(map[i], -1);
        for(int i =0 ; i < R ; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken())-1;
            int c = Integer.parseInt(st.nextToken())-1;
            int r1 = Integer.parseInt(st.nextToken())-1;
            int c1 = Integer.parseInt(st.nextToken())-1;
            bridge.add(new int[]{r, c, r1, c1});
        }

        for(int i =0 ; i < K ; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken())-1;
            int c = Integer.parseInt(st.nextToken())-1;
            cowPos.add(new int[]{r, c});
        }

        for(int i = 0 ; i < K ; i++){ // 소가 있는 위치를 기준으로 탐색 시작
            if(map[cowPos.get(i)[0]][cowPos.get(i)[1]] == -1){  // 이미 탐색이 된 곳이라면 pass  
                findWay(cowPos.get(i), i);
            }
        }

        int cnt = 0;
        for(int i =0 ; i < K-1 ; i++){
            for(int j = i+1 ; j < K ; j++){
                if(map[cowPos.get(i)[0]][cowPos.get(i)[1]] != map[cowPos.get(j)[0]][cowPos.get(j)[1]]) cnt ++;  // 영역이 다른 곳에 있으면 길을 건너야 하므로 cnt++
            }
        }

        System.out.println(cnt);
    }

    private static void findWay(int[] c, int area) {
        boolean[][] visited = new boolean[N][N];
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{c[0], c[1]});
        visited[c[0]][c[1]] = true;
        map[c[0]][c[1]] = area;
        while(!q.isEmpty()){
            int i = q.peek()[0];
            int j = q.poll()[1];
            next:for(int d = 0 ; d < 4 ; d++){
                int ni = i+di[d];
                int nj = j+dj[d];
                if(0<=ni&&ni<N && 0<=nj&&nj<N && !visited[ni][nj]){
                    for(int[] b: bridge){       // 둘 사이에 다리가 있는지 확인
                        if(b[0]==i&&b[1]==j && b[2]==ni&&b[3]==nj) continue next;
                        if(b[2]==i&&b[3]==j && b[0]==ni&&b[1]==nj) continue next;
                    }
                    q.offer(new int[]{ni, nj});
                    visited[ni][nj] = true;
                    map[ni][nj] = area; // 탐색한 자리의 영역을 표시
                }
            }
        }
    }
}