[백준 / BOJ] 14466 소가 길을 건너간 이유 6 (Java)

문제

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

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

N*N그리드에 K마리의 소가있고, R개의 길이있다.

각 소들이 상하좌우로 움직일수있을때, 길을 건너지않고 만날수없는 소들의 쌍을 구하는 문제다.

---

풀이

알고리즘 보다는, 문제 해석과 적절한 자료구조를 생각해 내는게 핵심인 문제였다.

 

처음에 문제를 봤을때 문제가 무엇을 원하는지 파악을 못했는데, 문제를 쉽게 축약해보면,

"길을 지나가지않고는 서로 만나지 못하는 소의 쌍을 구하라" 

가 된다.

 

길을 체크하는법 부터 생각해보자.

길이 다음과 같이 있다고 가정했을때,

2 2 2 3

이는, (2,2) (2,3)에 각각 길이 나있는것이아닌, 2,2와 2,3을 연결하는 길이 있는것이다 즉, 2,2에서 2,3으로 가는경우에만 체크를 해줘야한다.

위 길을 체크하는 법으로 크게 3가지를 생각했다.

 

1. 4차원 배열을 이용해 구현 = 메모리초과로 선언 불가능 (100^3이라서 배열의 크기가 1억이 된다.)

2. map을 이용해 구현 map(2,2,2,3) = true라면 길 있음, false = 길 없음 

-> 매번 4log(K)번 반복 (약 28번)

3. 3차원 배열을 이용해 구현 arr[y][x][dir] y,x에서 4방향으로 길이 있는지 체크한다.

-> 매번 4 반복

 

1번이 된다면 가장 빠르고 편하니 좋겠지만 아쉽게도 N이 최대 100이므로 선언조차 불가능하다.

2번으로 풀어도 TLE가 안나올거같긴한데, 그냥 더 빠른 3번을 이용해 풀었다.

 

방향을 체크하는 3차원 배열 path[y][x][dir]을 만든다.

이때, path는 다음과 같이 초기화 시킬것이다.

path[y][x][(상,하,좌,우)] = (경로 있음 true, 경로 없음 false)

문제에서 주어진 조건중, "길은 상하좌우로 인접한 두 목초지를 잇고"라는 문장 덕분에 위와같은 구조로 선언이 가능하다(길은 항상 4방향이므로)

 

코드는 다음과 같다.

                for(int dir = 0; dir < 4; dir++){
                    if(y1+dy[dir] != y2 || x1+dx[dir] != x2) continue;
                    path[y1][x1][dir] = true; // 두 경로를 연결
                    path[y2][x2][rev[dir]] = true; // 두 경로 연결
                    break;
                }

rev[dir]은 dir의 반대방향을 저장한 배열이다.

 

이제, 모든 소들부터 BFS를 수행해 답을 구해주면된다.

 

로직은 다음과 같다. (ret은 만든 소들의 쌍을 저장한 변수다.)

1. 모든 소들로BFS를 수행한다. 

2. 수행중 다른 소를 만난다면, ret+1을 해준다.

3. 수행중 길을 만난다면 해당 방향으로는 더 이상 탐색하지 않는다.

4. 최종적으로 구해진 ret에 중복을 제거해주기위해 나누기 2 를 하고, 나올수있는 모든쌍에서 뺀다.

 

    private int sumPairCow(){
        int ret = 0;
        while(!cowNumber.isEmpty()){
            Pair cow = cowNumber.poll();
            ret += getPairCow(cow.first, cow.second);
        }
        return getAllPair(K) - (ret/2);
    }
    
    private int getPairCow(int y, int x){
        boolean[][] check = new boolean[N+5][N+5];
        int ret = 0;
        Queue<Pair> cow = new LinkedList<Pair>();
        cow.add(new Pair(y,x));
        while(!cow.isEmpty()){
            int nowY = cow.peek().first;
            int nowX = cow.peek().second;
            cow.poll();
            if(check[nowY][nowX]) continue;
            if(cows[nowY][nowX] && (nowY != y || nowX != x)) ret++;
            check[nowY][nowX] = true;
            for(int dir = 0; dir < 4; dir++){
                int nextY = nowY + dy[dir];
                int nextX = nowX + dx[dir];
                if(nextY < 1 || nextY > N || nextX < 1 || nextX > N || path[nowY][nowX][dir] || check[nextY][nextX]) continue;
                cow.add(new Pair(nextY, nextX));
            }
        }
        return ret;
    }

위 로직(1,2,3,4번)을 구현한 코드다.

이해가 안가면 전체 소스코드를 보도록 하자.

 

시간복잡도는

- BFS탐색 : O(N*N)

- BFS호출횟수 : O(K)

- 탐색당 길 확인 : O(4) = O(1)

시간복잡도 : O(K(N^2))

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/14466%20%EC%86%8C%EA%B0%80%20%EA%B8%B8%EC%9D%84%20%EA%B1%B4%EB%84%88%EA%B0%84%20%EC%9D%B4%EC%9C%A0%206/Main.java

devxb/JJUNalgo