[Python] BOJ 21316 - 스피카

www.acmicpc.net/problem/21316

21316번: 스피카

 

# 입력되는 숫자만 다르고 그래프 모양은 같으므로 "Spica가 몇번인지 어떻게 판단할까??"

    생각해본 결과 그래프의 정점의 간선의 갯수로 판단을 해보자고 생각했다.

 

1. 별자리가 그래프라고 생각하고 x, y가 입력되면 서로 연결되있는 것으로 생각했다.

dic[x]에 y를 append하는 식으로 x정점과 연결되어있는 정점들을 모두 저장했다.

별자리를 보면 알 수 있듯이 정점과 연결된 간선의 갯수는 모두 1개, 2개, 3개 중 하나이다.

따라서 간선의 갯수가 1개, 2개, 3개인 정점들을 각각 one, two, three배열에 저장했다.

 

2. 예제에서 간선의 갯수가 3개인 별은 모두 4개로 3,4,7,9이다. (three배열)

  이 별들과 연결된 정점의 번호(for j in dic[i])는 다음과 같다.  ->  [2,7,4], [3,5,9], [3,6,8], [4,8,10]

 

3. 저 4개의 별들의 간선의 갯수(sum)는 다음과 같다. -> 8, 7, 6, 7

   이 중 sum이 6인 별이 Spica이다. 따라서 sum이 6인 별이 나오면 출력하고 break

 

dic = {}
one, two, three = [], [], []
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]) == 1:
		one.append(i)
	elif len(dic[i]) == 2:
		two.append(i)
	else:
		three.append(i)
for i in three:
	sum = 0
	for j in dic[i]:
		sum += len(dic[j])
	if sum == 6:
		print(i)
		break

 

(solved.ac 티어: 실버 1)