[백준] 21316번 스피카 [Python] - 그래프이론

별이 번호로 주어지고, 이어진 별의 정보가 주어졌을 때, 스피카를 찾는 문제

 

문제

 

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

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

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

입력

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

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

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

출력

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

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

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

 

행렬과 다음 정보 활용

스피카는 다른 별 3개와 이어져 있고,

그 3 별이 다른 별과 이어진 별의 개수의 합이 6이다.

import sys

# 별의 번호가 1번부터 시작
# 리스트의 인덱스는 0부터 시작
# 0은 버리는 칸이고, 1~12번 까지 담을 수 있게 총 13칸을 만듦
A = [[0]*13 for _ in range(13)]

# 선분이 12개라서 12번 반복 
for _ in range(12):
    a, b = map(int, sys.stdin.readline().split())
    
    # 이어진 두 별의 번호가 가리키는 행렬의 요소를 1로 입력 
    A[a][b], A[b][a] = 1, 1

li = []
# 스피카는 다른 3개의 별과 이어져 있음
for i in range(1, 13):
    if sum(A[i]) == 3:
        li.append(i)

# 스피가와 이어진 별 3개가 이어진 별의 수는 6이고, 
# li에 저장한 별 중에서 유일하다.
for p in li:
    s = 0
    for i, q in enumerate(A[p]):
        if q:
            s += sum(A[i])
    if s == 6:
        print(p)
        break

 

for문 한 번 줄이기,,,

import sys
A = [[0]*13 for _ in range(13)]
for _ in range(12):
    a, b = map(int, sys.stdin.readline().split())
    A[a][b], A[b][a] = 1, 1
for i in range(1, 13):
    s = 0
    if sum(A[i]) == 3:
        for j, p in enumerate(A[i]):
            if p:
                s += sum(A[j])
        if s == 6:
            print(i)
            break

 

 

행렬보다는 각 번호의 인덱스에 연결된 별의 번호를 추가하는 식으로 푸는 방법

import sys
A = [[] for _ in range(13)]
for _ in range(12):
    a, b = map(int, sys.stdin.readline().split())
    A[a].append(b)
    A[b].append(a)  
li = []
for i in range(1, 13):
    if len(A[i]) == 3:
        li.append(i)
for p in li:
    s = 0
    for i in A[p]:
        s += len(A[i])
    if s == 6:
        print(p)
        break

 

 

 

예제 입력 1 

1 2
2 3
3 4
4 5
3 7
4 9
6 7
7 8
9 8
9 10
10 11
12 11

예제 출력 1 

7