[백준] 6118(파이썬) - 숨바꼭질

[백준] 6118(파이썬) - 숨바꼭질

728x90

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

이 문제를 읽고 처음 든 생각은 BFS로 풀어야지 였다.

이 문제가 생각보다 간단했던 이유는 1번 노드부터 시작한다는 문제의 조건 때문이었다.

2차원 graph 배열을 만들어줘서 노드끼리의 관계를 나타내는 지표로 사용하고 visited_cnt를 만들어서 1번에서 각 노드에 갈 때까지의 거리를 기록해줬다.

기록해준 vistied_cnt 테이블 값을 갱신하면서 답을 구했고 문제에서 요구하는 최댓값에 관한 정보를 출력해주기 위해 max_num에 visited_cnt에서 가장 큰 값을 담아줘서 출력해줬다.

import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a) visited_cnt = [0]*(n+1) # 1번 헛간까지의 거리만 계산해주면 된다 def bfs(node): q = deque() q.append(node) visited_cnt[node] = 1 while q: node = q.popleft() for i in graph[node]: if visited_cnt[i] == 0: visited_cnt[i] = visited_cnt[node] + 1 q.append(i) # print(visited_cnt) bfs(1) max_num = max(visited_cnt) print(visited_cnt.index(max_num),max_num-1,visited_cnt.count(max_num))

from http://resilient-923.tistory.com/313 by ccl(A) rewrite - 2021-08-02 16:26:17