-
2660. [Python]회장뽑기Python_알고리즘/Gold V 2024. 7. 3. 13:02
1. 문제
https://www.acmicpc.net/problem/2660
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 너비우선탐색
3. 파이썬 코드
from collections import deque import sys input = sys.stdin.readline # 너비 우선 탐색 진행 def BFS(start): queue = deque([start]) # 친구의 점수를 리턴해줄 변수 max_value = 0 # 처음 시작점 0 으로 선언 distance[start] = 0 # queue가 존재할때 까지 반복 while queue: check = queue.popleft() for i in graph[check]: # 거리가 -1 인 경우 값을 이전 값 +1 로 갱신 후 queue에 추가 if distance[i] == -1: distance[i] = distance[check] + 1 queue.append(i) # max_value 갱신 if distance[i] > max_value: max_value = distance[i] return max_value N = int(input()) # 그래프로 접근 graph = [ [] for _ in range(N+1)] # -1, -1 나올때 까지 인풋 받기 while True: S, E = map(int,input().split()) if S == -1 and E == -1: break else: graph[S].append(E) graph[E].append(S) # min 값 저장 min_value = 10**9 # N+1 까지 반복 for i in range(1,N+1): # 거리 초기값 -1로 선언 distance = [-1] * (N+1) # i 에 대한 친구 점수 저장 value = BFS(i) # min 값 갱신 후 최소값이 변경됐기 떄문에 answer_list 초기화 if value < min_value: min_value = value answer_list = [(value, i)] # 값이 min 값과 같으면 리스트에 추가 elif value == min_value: answer_list.append((value,i)) # 최소 값, 길이 출력 print(min_value, len(answer_list)) ans = "" # 리스트 순회하며 ans 라는 str 에 저장 for answer in answer_list: ans += str(answer[1]) + " " print(ans.strip())
4. 문제를 풀고난 후 생각
- 너비 우선탐색을 진행하며 연결되는 친구의 개수를 체크해주는 문제이다.
- 각 인덱스 별 친구의 친구의 친구가 몇명인지 체크해가며 한 인덱스에서 모든 값을 순회하였을 경우 최고 점수를 체크해주고 그 값을 return 하여 회장 점수를 체크한다.
- 회장 점수를 체크하는 기준은 return 값이 min 값인지 아닌지 체크를 하며 min 값인 경우 리스트를 초기화 시켜주고 값이 같은 경우 리스트에 (값, 인덱스) 로 추가해줬다. ( 인덱스만 추가해줘도 됐을꺼 같다.... )
5. 문제를 푸는데 도움이 되는 지식
- 너비우선탐색(BFS)
'Python_알고리즘 > Gold V' 카테고리의 다른 글
23978. [Python]급상승 (0) 2024.07.01 10026. [Python]적록색약 (0) 2024.06.28 5972. [Python]택배 배송 (0) 2024.06.20 9251. [Python]LCS (0) 2024.06.16 12865. [Python]평범한 배낭 (0) 2024.06.05