[백준 / BOJ] 9874 Wormholes (Java)

문제

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

9874번: Wormholes

(의역으로, 틀린 해석이 있을수있습니다.)

농부 존의 취미인 고-에너지 물리학 실험은 역 효과를 가져왔다. 존의 실험으로 인해, N(1 <= N <= 12)개의 웜홀이 그의 농장 생겼다. (웜홀은 항상 짝수이며 농부존의 농장 2D로 나타내진다.)

 

농부 존의 계산에따르면, 웜홀은 N/2개의 연결로 이루어져있다.(한마디로 웜홀은 1대1 매칭이다) 예를들어, 웜홀 A와 B가 서로 연결되어있다면, 어떤 물체가 웜홀 A로 들어가면 B로 나온다.(반대의 경우도 마찬가지다)

 

이것은 안좋은 영향을 미칠수도있는데, 다음과 같은 이유 때문이다.

웜홀 A가 (0,0)에 있고, 웜홀 B가(1,0)에 있을때, 어떤 물체가 (1/2,0)지점에서 +x방향으로 이동한다고 가정해보자. 그렇다면 해당 물체는 처음에 웜홀B로 들어간후, 웜홀 A로 나오고 다시 웜홀 B로 들어가며 무한 루프에 빠져버린다.

 

농부존은 그의 농장어디에 웜홀이 생겼는지 정확히 알고있다. 또한, 그는 그의 소 베시가 항상 +x방향으로 이동하는것을 알고있다.(하지만 베시가 지금 어느 위치에 있는지는 모른다.)

농부존을 도와, 베시가 무한루프에 빠질수있는 시작위치가 한곳이라도 존재하는 웜홀 연결쌍을 구하자.

---

풀이

N이 최대 12이기때문에, 완전탐색으로 풀수있는 문제였다.

 

주의할점이

웜홀의 위치가 최대 10억까지 갈수있다. 즉, 행렬을 사용해서 웜홀의 위치를 표현하지못하기때문에,

동적 배열을 사용해서 웜홀의 위치를 표현해줘야하며, +x방향으로 이동했을때 빠지는 웜홀의 위치또한 동적배열에서 탐색을 해가며 찾아줘야한다.

 

알고리즘은 다음과 같다.

 

1. 백트래킹을 이용해 웜홀을 연결할수있는 모든 경우의 수를 만든다.

- 이때, 웜홀 연결쌍을 중복해서 만들지 않도록 주의해야한다.

 

코드

    private int connectWormHole(int idx, int connect){
        int ret = 0;
        if(connect == N){
            for(int i = 0; i < N; i++){
                if(loopCheck(wormHoles.get(i))) return 1;
            }
            return 0;
        }
        for(int A = idx; A < N; A++){
            if(connected[A]) continue;
            connected[A] = true;
            for(int B = A+1; B < N; B++){
                if(connected[B]) continue;
                connected[B] = true;
                wormHoles.get(A).connect(wormHoles.get(B));
                ret += connectWormHole(A+1, connect+2);
                connected[B] = false;
            }
            connected[A] = false;
        }
        return ret;
    }

 

2. 모든 웜홀을 연결했을때, 해당 연결쌍에서 루프가 하나라도 존재 하는지 확인한다.

- 루프가 하나라도 존재하는지 확인하기위해서 모든 시작위치에서 시작한다. 시작위치는 처음들어가는 웜홀의 위치로 지정했다.

 

코드

    private boolean loopCheck(Hole hole){ // true : loop, false : noloop
        boolean[] visited = new boolean[N+5];
        while(true){
            if(visited[hole.idx]) return true; // 이미 들어갔던 웜홀인지 체크 맞다면 return true
            visited[hole.idx] = true; // 아니라면 true
            hole = hole.getHole(); // 연결된 웜홀로 나오기
            hole = nextHole(hole); // +x 방향으로 이동했을때 다음 구멍 찾기
            if(hole == null){ // 다음 구멍이 없다면, 
                return false;
            }
        }
    }
    
    private Hole nextHole(Hole hole){
        for(int i = 0; i < N; i++){
            Hole wormHole = wormHoles.get(i);
            if(wormHole.y == hole.y && wormHole.x > hole.x) return wormHole;
        }
        return null;
    }

 

3. 모든 시작지점에서 시작했을때, 루프가 생기지않았다면, 0 아니라면 1을 반환한다.

 

모든 연결쌍에대해 위 과정을 반복한후, 반환값을 다 더하면 답이나온다.