아이디어
- bfs탐색을 통해 친구의 친구의 친구.... 를 시작점 부터의 거리로 두면 될 것 같다.
- 근데 정확히 점수가 어떻게 반영되는지는 모르겠다. 일단 bfs 탐색 해보자.
풀이
import sys; from collections import deque, defaultdict
def bfs(v):
visited = [-1] * (N + 1) # bfs함수 내에서 visited를 초기화
visited[v] = 0 # 시작점은 0으로 초기화
Q.append(v)
while Q:
v = Q.popleft()
for w in G[v]:
if visited[w] == -1:
visited[w] = visited[v] + 1
Q.append(w)
return max(visited) # visited의 최대값이 점수이다.
N = int(sys.stdin.readline())
G = [[] for _ in range(N+1)]
while True:
u, v = map(int, sys.stdin.readline().split())
if u == -1 and v == -1:
break
G[u].append(v)
G[v].append(u)
Q = deque()
result = 0xfffff
for i in range(1, N+1):
tmp = bfs(i)
if tmp < result: # 회장이 될 수 있는 점수 찾기
result = tmp
candidate = []
for i in range(1, N+1):
if bfs(i) == result:
candidate.append(i) # 회장 후보들을 candidate에 저장
candidate.sort()
print(result, len(candidate))
print(*candidate)
후기 및 해설
- 백준의 예제를 bfs탐색을 통해 visited를 보니 visited의 가장 큰 값이 점수임을 확인했다.
- 그다음은 간단하다. 각 개인의 점수의 최소값을 result로 잡아주고
- 개인의 점수가 result인 사람을 candidate에 넣는다.
의문점
- 처음 bfs함수 내에서 visited를 다 0으로 하고, 반복문 안에서 visited[w] = visited[v] + 1로 설정하였는데,
- 60% 쯤에서 틀렸다고 나왔다.
- 그래서 visited를 -1로 초기화 하고 시작점을 0을 넣어주고, 방문점은 +1 해줬다.
- 이 방법을 사용하니 통과됐다. 무슨차이인지 잘 모르겠지만, 깊게 생각하면 너무 시간이 낭비된다..
- 일단 이 정도로만 알아두자.
