[Python] 6118번 숨바꼭질

✏️ 문제

 

 

문제 파악

인접리스트를 활용해 예제 1과 같은 경우 1과 연결된 2, 3를 배열[1]에 대입하고 2와 연결된 1, 3, 4, 5를 배열[2]를 넣으면서 풀면 된다.

처음 찾는 1번을 기준으로 각 숫자의 거리를 visited의 배열에 담는다.

그 후 배열의 메소드인 index(), max(), count()를 활용해서 결과를 출력한다.

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

코드

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

n, m = map(int, input().split())
graph = [[] * (n+1) for _ in range(n+1)]
visited = [0] * (n+1)
d = 0

for _ in range(m):
  x, y = map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)

def bfs(v):
  q = deque([v])
  visited[v] = 0
  
  while q:
    node = q.popleft() 

    for neighbor in graph[node]:
      if visited[neighbor] == 0:
        visited[neighbor] = visited[node] + 1
        q.append(neighbor)
        
bfs(1)
visited[1] = 0 # visited[1]의 값이 bfs 돌고나면 바뀌므로 마지막에 0으로 한 번 더 대입
print(visited.index(max(visited)), max(visited), visited.count(max(visited)), sep=' ')

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS