[백준/파이썬/그래프] 21316번 스피카 코딩테스트 연습풀이

문제 출처: https://www.acmicpc.net/problem/21316

21316번: 스피카

 

문제

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

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

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

 

입력

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

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

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

 

출력

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

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

 

정답

dic = {}
arr = []
for _ in range(12):
	x, y = map(int,input().split())
	if x in dic:
		dic[x].append(y)
	else:
		dic[x] = [y]
	if y in dic:
		dic[y].append(x)
	else:
		dic[y] = [x]
for i in dic:
	if len(dic[i]) == 3:
		arr.append(i)
for i in arr:
	sum = 0
	for j in dic[i]:
		sum += len(dic[j])
	if sum == 6:
		print(i)
		break

간선이 3개인 점을 찾은 후에 점과 근처 4개의 점 간선의 합이 6인 점을 구하면 성공