백준 21316 - 스피카 (자바 - 그래프)

https://www.acmicpc.net/problem/21316

21316번: 스피카

 

* 문제 요약

 

위 그림은 처녀자리 중 12개의 별을 12개의 선분으로 이어만든 그림이다.

시은이는 임의로 각 별에 1부터 12까지의 서로 다른 정수 번호를 부여하고, 12개의 정수 쌍으로 각 선분이 어떤 두 별을 잇는지 기록하였다. 하지만 어떤 별에 어떤 번호를 부여했는지 잊어버렸다고 한다.

선분들의 정보가 주어질 때, 가장 밝은 별인 Spica 가 몇 번 별이었는지 알려주자.

 

* 입력

입력은 12개의 줄로 주어진다.

각 줄에는 서로 다른 두 개의 정수 x,y  가 주어지며, 두 별 x와 y를 잇는 선분이 있음을 의미한다.

반드시 그림과 같은 모습임이 보장된다.

 

* 출력

입력으로 주어진 그래프에서 Spica 는 몇 번 별인지 출력하라.

번호에 해당하는 정수 하나를 출력하면 된다.

 

* 예시

 

* 해결 과정

Spica 별의 특징은 기본적으로 자신과 연결된 별이 3개 있으면서 각 3개의 별이 다른 별과 연결되어 있는 갯수가 각각 3개, 2개, 1개인 경우에 해당된다. 이 특징을 파악한다면 금방 풀 수 있는 문제이다.

주어진 입력대로 BFS 탐색 중 그래프상에서 연결되어 있는 노드를 3개 가지고 있는 노드가 발견될 경우 다음과 같이 처리한다.

1. 연결되어 있는 노드 하나를 대상으로 몇 개의 다른 별과 연결되어 있는지 확인한다.

2. 연결되어 있는 대상이 3개인 경우 이미 앞전에 3개가 연결된 별이 발견된게 아니라면 three 변수를 true 로 초기화한다.

3. 연결되어 있는 대상이 2개인 경우 이미 앞전에 2개가 연결된 별이 발견된게 아니라면 two 변수를 true 로 초기화한다.

4. 연결되어 있는 대상이 1개인 경우 이미 앞전에 1개가 연결된 별이 발견된게 아니라면 one 변수를 true 로 초기화한다.

5. 만약 one, two, three 변수가 모두 true 라면 현재 탐색중인 노드의 번호를 반환값으로 돌려주고 탐색 메소드를 종료시킨다.

6. 그렇지 않은 경우 BFS 탐색을 종료한다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static HashMap<Integer, List<Integer>> hashMap = new HashMap<>();
    static boolean[] visited = new boolean[13];

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 12; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);

            List<Integer> aList = new ArrayList<>();
            List<Integer> bList = new ArrayList<>();
            if (hashMap.containsKey(a)) {
                aList = hashMap.get(a);
            }
            aList.add(b);
            hashMap.put(a, aList);

            if (hashMap.containsKey(b)) {
                bList = hashMap.get(b);
            }
            bList.add(a);
            hashMap.put(b, bList);

            if (a > b) {
                min = Math.min(min, b);
            } else {
                min = Math.min(min, a);
            }
        }

        int result = bfs(min);

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private int bfs(int min) {
        Queue<Integer> needVisit = new LinkedList<>();
        needVisit.offer(min);
        visited[min] = true;

        int result = 0;
        while (!needVisit.isEmpty()) {
            int number = needVisit.poll();

            List<Integer> list = hashMap.get(number);
            // spica 인지 확인
            if (list.size() > 2) {
                boolean one = false;
                boolean two = false;
                boolean three = false;

                for (int i = 0; i < 3; i++) {
                    int connect = list.get(i);

                    if (hashMap.get(connect).size() == 3 && !three) {
                        three = true;
                    } else if (hashMap.get(connect).size() == 2 && !two) {
                        two = true;
                    } else if (hashMap.get(connect).size() == 1 && !one) {
                        one = true;
                    }
                }
                if (one && two && three) {
                    result = number;
                    break;
                }
            }
            // 방문 필요큐에 연결 노드 저장
            for (int i = 0; i < list.size(); i++) {
                if (!visited[list.get(i)]) {
                    needVisit.offer(list.get(i));
                    visited[list.get(i)] = true;
                }
            }
        }
        return result;
    }
}

 

찾고자 하는 Spica 의 특징을 알고나면 BFS 탐색 도중 Spica 의 특징을 가지고 있는 노드를 찾아서 반환만 해주면 되는 그래프 탐색 문제이다.