[백준 21316번] 스피카

문제 링크: 21316번 제목

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

 

"반드시 그림과 같은 모습임이 보장된다"에서, 그림을 통해 Spica의 특징(?), 즉 Spica를 변별해낼 수 있는 유일한 성질을 발견해야 한다는 것을 알 수 있다.

점 i와 연결되는 점의 개수를 f(i)라고 하고, 점 i와 연결되는 점을 i[1], i[2], ..., i[n]이라고 하면, Spica만 유일하게 f(i) = 3이면서 f(i[1])+f(i[2])+...+f(i[n]) = 6이다.

 

 

이 그림에서, Spica는 7이고, 7과 연결되는 점은 6, 3, 8이다. 그리고 f(6)= 1, f(3) = 3, f(8) = 2이다. 반면 f(i) = 3을 만족하는 다른 점들, 즉 3, 4, 9의 경우 f(i[1])+f(i[2])+...+f(i[n]) = 6을 만족하지 않는다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        int[] numEdges = new int[13];
        ArrayList<Integer>[] graph = new ArrayList[13];
        for (int i = 1; i < 13; i++) graph[i] = new ArrayList<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 12; i++) {
            StringTokenizer line = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(line.nextToken());
            int b = Integer.parseInt(line.nextToken());
            numEdges[a]++;
            numEdges[b]++;
            graph[a].add(b);
            graph[b].add(a);
        }

        int spica = - 1;
        for (int i = 1; i <= 12; i++) {
            if (numEdges[i] != 3) continue;

            int sum = 0;
            for (int adj : graph[i]) sum += numEdges[adj];
            if (sum == 6) {
                spica = i;
                break;
            }
        }

        System.out.println(spica);
    }
}