백준 21316 (C++) 스피카

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

문제 이해

조건에 따르면 7번 별이 스피카이다.
12줄에 걸쳐 그래프(별자리) 정점(별)과 간선 정보가 주어진다.

문제의 입력에서

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

고 했으므로 주어지는 그래프는 모두 동형이다.

따라서 매 테스트케이스 마다 12줄에 걸쳐 동일한 그래프의 정점과 간선 정보가 주어지지만,
서로 다른 두 개의 정수 x, y 또한 바뀔 것이다.

그러므로

우리는 매번 바뀌는 테스트 케이스에서,
(조건의) 저 7번 자리에 위치하는 별의 번호를 출력해야한다.

그렇다면 어떤 별이 (조건의) 7번 자리인 것을 어떻게 알아낼까?

인접한 정점의 차수

7번과 인접한 정점들을 보자. 7번의 차수는 3이고,
인접한 정점은 3, 6, 8번 별이다.

인접한 정점들의 차수는

6번은 1,
8번은 2,
3번은 3이다.

이러한 조건을 가진 정점은 7번이 유일하다.

동일 조건을 찾는 알고리즘을 작성하면 된다.

양방향 그래프의 입력을 2차원 배열의 인접 행렬로 저장하고,
각 노드의 차수를 증가 시킨다.

그래프의 노드를 탐색하다가 차수가 3인 경우
그 노드의 인접한 정점을 탐색
인접한 정점의 차수를 각각 확인함

코드

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 13;
const int edge = 12;
int adj[MAX][MAX];
int degree[MAX];

void spica() {
    for (int i = 1; i <= edge; i++) {
        bool first = false;
        bool second = false;
        bool third = false;
        
        if (degree[i] == 3) {
            for (int j = 1; j <= edge; j++) {
                if (adj[i][j] && degree[j] == 1) first = true;
                if (adj[i][j] && degree[j] == 2) second = true;
                if (adj[i][j] && degree[j] == 3) third = true;
            }
        }
        if (third && second && first) cout << i;
    }
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for (int i = 0; i < edge; i++) {
        int x, y; // 1 <= x,y <= 12
        cin >> x >> y;
        adj[x][y] = 1;
        adj[y][x] = 1;
        degree[x]++;
        degree[y]++;
    }
    // print degree of each nodes
    // for (int i = 1; i <= edge; i++) cout << degree[i] << '\n';
    spica();
    
    return 0;
}

여담

항상 함수를 짜놓고 main()함수에 함수 호출을 깜빡한다...
이번에도 짜놓고 아무것도 출력되지 않길래 약 2분을 화멍(화면을 보며 멍때리기)했다...

혼자 백준 챌린지 21일째이다 얏호~