[백준 java] 소가 길을 건너간 이유 14466

🔗 문제링크 🔗

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

---

🌟 생각 흐름 🌟

먼저 가지 못하는 길을 저장해야 한다고 생각했습니다.

만약 리스트 형태로 저장하게 된다면 탐색에 너무 많은 시간이 걸리고 map의 사이즈가 100*100이므로  배열의 형태로 저장하는 것이 이득이라 생각하였습니다. 

 

문제는 길의 startx, starty, endx, endy 형태로 주어지기 때문에 어느방향으로 길이 있는지 저장해야 합니다. 

따라서 direction 방향에 따라 확인해보면서 start에서 dircetion으로 갔을 때 end와 같으면 해당 방향으로 길이 있다고 저장하였습니다

문제는 여기서 해당 방향과 반대 방향에 대한 길도 가지 못하는것을 저장해야 합니다. 

즉 2,2에서 오른쪽으로 간다면 2,3에서는 왼쪽방향으로 길이 있어 가지 못하는 상황을  생각하고 반대방향에 대한 길도 통행이 불가능함을 처리해야 합니다.

저는 여기서 방향을 (위쪽, 오른쪽, 아래, 왼쪽) 형태로 저장하여 end 위치에서 현재 방향 인덱스에 + 2를 한 방향을 가지 못한다고 처리하였습니다.

(ex:  start 위치에서 오른쪽으로 가는 1번 direction 방향이라면,  end 위치에서는 [1+2=3] 3의 위치인 왼쪽 방향을  가지 못한다고 저장)

 

그 이후에는 소의 위치를 map [x][y][4]에 저장하고, 소 각각의 배열도 두어 저장하였습니다. 

이는 나중에 소를 마주쳤을 때 쉽게 확인하고 시작하는 소의 위치를 지정하기 위해서 이렇게 하였습니다.

 

이후에는 bfs로 탐색을 하면 됩니다. 가지 못하는 길인 경우는 가지 못하게 하고 만약 마주치는 소가 있다면 소의 개수를 세고 

전체 소에서 자신과 마주친 소의 수를 빼고 이의 합을 계산하였습니다 이후에는 마주치지 못하는 소의 쌍 이기 때문에 2로 나누어 출력하였습니다.

 

---

🍳 코드 🍳

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

public class Main {
    private static final int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static int[][][] map; // 0 위 , 1 오른쪽, 2 아래 , 3 왼쪽 , 4 소가 있다면 소의 번호
    private static int size; //지도의 사이즈
    private static int[][] cows; //소들의 위치

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        size = Integer.parseInt(st.nextToken());
        int cow = Integer.parseInt(st.nextToken());
        int command = Integer.parseInt(st.nextToken());

        map = new int[size][size][5];
        while (command-- > 0) {
            st = new StringTokenizer(br.readLine());
            int startX = Integer.parseInt(st.nextToken()) - 1;
            int startY = Integer.parseInt(st.nextToken()) - 1;
            int endX = Integer.parseInt(st.nextToken()) - 1;
            int endY = Integer.parseInt(st.nextToken()) - 1;

            for (int i = 0; i < 4; i++) {
                int[] dir = dirs[i];
                if (startX + dir[0] == endX && startY + dir[1] == endY) {
                    map[startX][startY][i] = -1; //이동하지 못한다
                    map[endX][endY][(i + 2) % 4] = -1; //반대방향도 이동하지 못하는것을 저장
                    break;
                }
            }
        }

        cows = new int[cow][2];
        for (int i = 0; i < cow; i++) {
            st = new StringTokenizer(br.readLine());
            int cowX = Integer.parseInt(st.nextToken()) - 1;
            int cowY = Integer.parseInt(st.nextToken()) - 1;
            cows[i] = new int[]{cowX, cowY}; //소의 위치를 저장한다.
            map[cowX][cowY][4] = i + 1;// 위치한 소의 번호를 저장한다.
        }

        int sum = 0;
        for (int i = 0; i < cow; i++) {
            sum += (cow - 1 - bfs(i)); //만난소의 숫자와 자기 자신을 뺀다
        }

        System.out.println(sum / 2); // 소의 쌍 이기때문에
    }

    private static int bfs(int idx) {
        boolean[][] visited = new boolean[size][size];
        visited[cows[idx][0]][cows[idx][1]] = true;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(cows[idx]);
        int visitCnt = 0; // 만난 소의 수

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int[] dir = dirs[i];
                int mvx = now[0] + dir[0];
                int mvy = now[1] + dir[1];

                if (mvx < 0 || mvy < 0 || size <= mvx || size <= mvy || visited[mvx][mvy]) {
                    continue;
                }
                if (map[now[0]][now[1]][i] == -1) {
                    continue; //갈수 없는 길}
                }

                if (map[mvx][mvy][4] != 0) { //소를 만났다
                    visitCnt++;
                }
                visited[mvx][mvy] = true;
                queue.add(new int[]{mvx, mvy});
            }
        }
        return visitCnt;
    }
}