2660번 회장뽑기 : 파이썬(Python)

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

문제

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 붙어 있다. 마지막 줄에는 -1이 두 개 들어있다.

출력

첫째 줄에는 회장 후보의 점수와 후보의 수를 출력하고, 두 번째 줄에는 회장 후보를 오름차순으로 모두 출력한다.

문제 요소 찾기

문제의 핵심은 왕따다.. ㅋㅋ

농담이고, 쌓이면 쌓일수록 점수가 높아진다.

여기서 핵심은 점수가 가장 낮은 사람이 회장이 되는 것이다.

또 입력을 보면 50명 이하, 점수가 가장 낮은..? 여기서 바로 플로이드 워셜임을 알아챌 수 있어야 한다.

(플로이드 워셜은 시간복잡도가 (N^3)이지만, 그만큼 구현도 쉽기 때문에 데이터가 많지 않으면 BFS 대신 쓰는 편이다.)

1. 플로이드 워셜 방법은 dp와 방법이 거의 유사하다. dp처럼 모든 그래프를 "무한"의 숫자로 만들겠다.

INF = int(1e9) # 10억으로 초기화

n = int(input())
dp = [[INF] * (n+1) for _ in range(n+1)] # List comprehension으로 n+1개의 2차원 리스트 만듦
# ex) 5라면
# [1e9, 1e9, 1e9, 1e9, 1e9, 1e9]
# [1e9, 1e9, 1e9, 1e9, 1e9, 1e9]
# [1e9, 1e9, 1e9, 1e9, 1e9, 1e9]
# [1e9, 1e9, 1e9, 1e9, 1e9, 1e9]
# [1e9, 1e9, 1e9, 1e9, 1e9, 1e9]
# [1e9, 1e9, 1e9, 1e9, 1e9, 1e9]

2. -1이 나올경우만 멈춰주기 때문에 반복을 예측할 수 없다. while로 무한루프를 돌려서 값을 받고, dp에 값을 초기화해준다.

while True:
	a, b = map(int, input().split())
    if a == b == -1: break # a == -1 and b == -1 
    dp[a][b] = 1
    dp[b][a] = 1 # a,b는 친구인거니까 1로 초기화 해준다.

1로 초기화 하는 이유를 간단히 설명하면 본인과 친구라면 무조건 1점, 친구의 친구면 2점.. 이런식이니 직통으로 친구면 무조건 1점이니 1로 초기화..(나도 뭐라는지 모르겠지만.. 암튼 그런 느낌)

3. 자기 자신이랑은 친구가 될 수 없으니, 자기 자신의 경우는 0으로 초기화해준다.

for i in range(1, n+1):
	dp[i][i] = 0

4. 이제 3중 for문을 돌려 모든 그래프를 순회하면서 값을 바꿔준다.

for k in range(1, n+1):
	for i in range(1, n+1):
	     for j in range(1, n+1):
        	if dp[i][j] == 1 or dp[i][j] == 0: continue # 이미 값을 초기화한 애들이니까
           	else: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

그래프를 예를 들면 무한이 큰지, i -> k -> j 로 가는 수가 작은지 비교. 친구의 친구를 확인.

k번과 연결된 친구들을 확인하는 것이다. k와 친구인 i, j를 확인. 만약 i, j중 k와 친구가 아니라면 그 그래프 인덱스에는 무한의 값이 들어있을테니 당연히 전자가 클 것이다. 이렇게 전체 반복 한다.

5. for문을 돌고 나오면 값이 초기화 되어있을테니 점수를 집계한다.

li = []
for i in range(1, n+1): li.append(max(dp[i][1:]) # 0번 인덱스는 무한이니까 제외하기 위해
m = min(li) # 그 중에 가장 작은 수가 회장이니 작은수 찾기
print(m, li.count(m)) # 가장 작은 수와, 동점이 몇명인지 찾기
for a, b in enumerate(li, start=1): # b엔 값, a엔 인덱스가 들어가게 하는 enumerate, start=1은 인덱스 시작값
   if b == m: print(a, end=" ")

최종 완성 코드

import sys
input = sys.stdin.readline

INF = int(1e9)

n = int(input())
dp = [[INF] * (n+1) for _ in range(n+1)]

while True:
    a, b = map(int, input().split())
    if a == b == -1: break
    dp[a][b] = 1
    dp[b][a] = 1
    
for i in range(1, n+1):
    dp[i][i] = 0

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dp[i][j] == 1 or dp[i][j] == 0: continue
            else: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

li = []
for i in range(1, n+1): li.append(max(dp[i][1:]))
m = min(li)
print(m, li.count(m))
for a, b in enumerate(li, start=1):
    if b == m: print(a, end=" ")

봐주셔서 감사합니다. 피드백이나 질문은 댓글 달아주시면 답변 드리겠습니다!

현준의 코딩연습

2660번 회장뽑기 : 파이썬(Python)