백준/ Gold 5 문제 , 백준 파이썬 2660 , 회장뽑기 [BFS]

백준/ Gold 5 문제 , 백준 파이썬 2660 , 회장뽑기 [BFS]

 

 

 

풀이 시간

 

27분 정도

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
문제를 처음에 이해하는데 좀 시간이 걸림. 결국 각 호출값이 가지는 가장 큰값들을 저장해두고 그중에서 가장 작은 값을 가진 사람들이 회장 후보가 됨.

 

 

문제 출처

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

2660번: 회장뽑기

 

 

풀이

 

 

1. 기본 세팅

 

1. 상하좌우 움직임.

 

2. N 입력받기

 

3. N+1 크기의 리스트 선언

 

4. while 문 통해서 -1 -1 입력 될때까지 양방향 넣어주기

 

 

 

 

2. BFS

 

bfs 함수내에 cnt 리스트를 선언해주고 dq를 돌리면서 카운트 해줄 것이다.

 

이때 호출 부분은 1로 처음에 선언해줘서 재탐색을 방지하고 

 

가장 큰값을 찾을때는 호출 부분에 해당하는 인덱스를 제외하고 찾아준다.

 

연결이 가장 큰 길이가 해당 인덱스가 갖게되는 값이므로 이 값을 return 해준다.

 

 

3.  BFS 호출 및 처리

 

모든 인덱스들을 다 한번씩 bfs 호출을 해주고 return 값을 result 리스트에 저장해준다.

 

그 중에서 가장 작은 값이 회장후보에 오를 점수이고

 

이 점수에 맞는 후보들을 골라내준다.

 

출력시 MIN 을 그대로 출력하면 안되고,

 

 

bfs 함수내에서 시작점을 0이 아닌 1로 선언했으므로 결과값들이 다 1씩 증가하였다.

 

그러므로 MIN에서 1을 뺀 값을 출력시키면 된다.

 

 

 

정답

 

from collections import deque
import sys
input=sys.stdin.readline

N=int(input())
l=[[] for _ in range(N+1)]
while True:
    a,b=map(int,input().split())
    if a==-1 and b==-1:
        break
    l[a].append(b)
    l[b].append(a)


def bfs(x):
    dq=deque()
    dq.append(x)
    cnt=[0 for _ in range(N+1)]
    cnt[x]=1
    while dq:
        a=dq.popleft()
        for i in l[a]:
            if cnt[i]==0:
                cnt[i]=cnt[a]+1
                dq.append(i)
    del(cnt[x])
    return max(cnt)
        
result=[]
for i in range(1,N+1):
    result.append(bfs(i))

MIN=min(result)
answer=[]
for i in range(N):
    if result[i]==MIN:
        answer.append(i+1)
print(MIN-1, len(answer))
print(*answer)