[백준, JAVA]9874번, Wormholes

문제 링크

9874번: Wormholes

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

주관적인 문제 해석!

 

농부 존의 취미인 고에너지 물리 실험을 주말에 수행하다가 역효과가 발생하여, 2D모양의 농장에 N개의 웜홀이 생겼습니다.

 

그의 계산에 따르면, 웜홀은 N/2개로 연결되 쌍으로 생성될 것입니다. 예를 들어 A와 B가 연결되었을 때 A로 들어가면 B로 나오고 B로 들어가면 A로 나오게 된다. 이것은 불쾌한 상황이 연출될 수 있다. A(0, 0), B(1, 0)의 웜홀이 연결되고 소가 (0.5, 0)에서 +x 방향으로 이동하면 B웜홀을 타고 A로 이동한 뒤 다시 B로 다시 이동하는 무한 순환에 갇히게 된다!

 

농부 존은 웜홀의 위치는 정확히 알고 있지만 소의 위치는 현재 어디있는지 모른다. 소는 항상 +x 방향으로만 이동한다. 좋지 않은 위치에서 시작하여 무한 순환에 갇히도록 하는 중복되지 않는 웜홀의 쌍을 만드는 개수를 구하는 것으로 농부 존을 도와주어라.

 

BFS

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심

1. N개의 웜홀이 주어지며 각 2개씩 쌍을 이룬다.

2. 소는 항상 +x 방향으로만 이동한다.

3. 소가 무한 순환에 빠지는 경우로 쌍이 맺어진 개수를 결과로 출력합니다.

 

 

웜홀이 묶이는 모든 쌍을 백트래킹으로 만들었습니다.

 

웜홀이 모두 묶이면 소가 각 웜홀에서 이동(+x)을 시작하여 무한 순환에 걸리는지 확인합니다.

 

무한 순환에 걸리면 해당 웜홀의 묶음은 농부 존이 만족하는 것으로 +1을 진행한다.

 

 

예제입력 1

 

웜홀 위치

 

1 : (0, 0)

2 : (1, 0)

3 : (1, 1)

4 : (0, 1)

 

웜홀이 1-2, 3-4로 묶일 때

 

소가 1번 웜홀에서 출발!

1 -> 2 -> .......쭉 +x방향으로 이동

무한 순환에 빠지지 않는다.

 

소가 2번 웜홀에서 출발!

2 -> 1 -> +x > 2 > 1 > .... 무한 순환

무한 순환에 빠지기 때문에 농부 존이 만족하는 쌍이다.

 

웜홀이 1-3, 2-4로 묶일 때

 

소가 1번 웜홀에서 출발!

1 -> 3 -> .......쭉 +x방향으로 이동

무한 순환에 빠지지 않는다.

 

소가 2번 웜홀에서 출발!

2 -> 4 -> +x > 3 -> 1 -> +x -> 2 -> ...... 무한 순환

무한 순환에 빠지기 때문에 농부 존이 만족하는 쌍이다.

 

웜홀이 1-4, 2-3로 묶일 때

 

소가 1번 웜홀에서 출발!

1 -> 4 -> +x -> 3 -> 2 -> .......쭉 +x방향으로 이동

무한 순환에 빠지지 않는다.

 

소가 2번 웜홀에서 출발!

2 -> 3 -> .......쭉 +x방향으로 이동

무한 순환에 빠지지 않는다.

 

소가 3번 웜홀에서 출발!

3 -> 2 -> .......쭉 +x방향으로 이동

무한 순환에 빠지지 않는다.

 

소가 4번 웜홀에서 출발!

4 -> 1 -> +x -> 2 -> 3 -> .......쭉 +x방향으로 이동

무한 순환에 빠지지 않는다.

 

 

모두 무한 순환에 빠지지 않기 때문에 농부 존에 만족하는 웜홀의 쌍이 아니다.

 

농부 존에 만족하는 웜홀의 묶음 2개를 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용해서 웜홀에 대한 정보를 나누었습니다.
• Collections.sort를 이용하여 x값 기준으로 오름차순 정렬하였습니다.
• setWormhole를 실행하여 무한 순회에 걸리는 웜홀 묶음의 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• setWormhole는 백트래킹으로 모든 웜홀의 묶음을 만들어서 moveCow함수를 실행합니다.
• moveCow는 소가 움직임을 하면서 무한 순회에 걸리는지 확인하는 함수입니다.
• searchNextHole는 소가 움직이면서 +x방향으로 갈 때 다음 웜홀에 빠지는 것을 확인하는 함수입니다.

※Collections.sort를 사용하는 이유는 +x방향으로 이동하면 x값이 작은 값부터 웜홀을 타기 때문입니다.

 

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

public class Main {
	//웜홀 정보 관련 클래스
    static class position implements Comparable<position>{
        int x, y, ci;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
        //웜홀 연결 설정
        public void connect(int index){
            ci = index;
        }
        //x좌표 기준 오름차순 정렬
        @Override
        public int compareTo(position o) {
            return this.x - o.x;
        }
    }
    static int N, answer = 0;
    static boolean[] visited;	//웜홀 방문 배열
    static ArrayList<position> wormhole = new ArrayList<>();	//웜홀 정보 저장 리스트
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        visited = new boolean[N];
        //웜홀에 대한 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            wormhole.add(new position(x, y));
        }
        Collections.sort(wormhole);	//웜홀 x값 기준 오름차순 정렬
        setWormhole(0, 0);	//무한 순환에 걸리는 웜홀 묶음 구하는 함수 실행
        bw.write(answer + "");		//무한 순환 걸리는 웜홀 묶음 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //백트래킹으로 웜홀의 묶음을 만드는 함수
    static void setWormhole(int count, int index){
        if(count == N){		//묶음 완성!
            //무한 순환인지 확인하는 함수 실행
            for(int i=0;i<N;i++){
                if(moveCow(i)){	//무한 순환에 만족할 때
                    answer++;
                    return;
                }
            }
        }
        for(int i=index;i<N;i++){
            if(visited[i])
                continue;
            visited[i] = true;
            for(int j=i+1;j<N;j++){
                if(visited[j])
                    continue;
                visited[j] = true;
                wormhole.get(i).connect(j);
                wormhole.get(j).connect(i);
                setWormhole(count + 2,i+1);
                visited[j] = false;
            }
            visited[i] = false;
        }
    }
    //소가 +x방향으로 움직이면서 웜홀을 타서 무한 순환에 걸리는지 확인하는 함수
    static boolean moveCow(int index){
        boolean[] use = new boolean[N];
        while(true){
            if(use[index])	//무한 순회에 걸렸을 때
                return true;
            use[index] = true;
            int x = wormhole.get(wormhole.get(index).ci).x;
            int y = wormhole.get(wormhole.get(index).ci).y;
            index = searchNextHole(x, y);
            if(index == -1)
                return false;
        }
    }
    //+x방향으로 이동하면서 다음 웜홀을 찾는 함수
    static int searchNextHole(int x, int y){
        for(int i=0;i<N;i++){
            if(wormhole.get(i).y == y && wormhole.get(i).x > x)
                return i;
        }
        return -1;	//다음 웜홀이 존재하지 않을 때
    }
}