[백준][Python] 6118 숨바꼭질

그래프, bfs / 실버 1

🙈

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

6118번: 숨바꼭질

 

 

내 풀이

from collections import deque

def bfs(s):
    q = deque()
    q.append(s)
    visited[s] = True

    while q:
        c = q.popleft()

        for i in arr[c]:
            if not visited[i]:
                visited[i] = True
                distance[i] = distance[c] + 1
                q.append(i)

N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]
visited = [False] * (N+1)
distance = [0] * (N+1)

for _ in range(M):
    num1, num2 = map(int, input().split())
    arr[num1].append(num2)
    arr[num2].append(num1)

bfs(1) # 시작점

ans = max(distance) # 가장 먼 거리
print(distance.index(ans), ans, distance.count(ans))

bfs(너비 우선 탐색)로 풀었다.

 

 

코드 설명

 

인덱스를 직관적으로 사용하기 위해 리스트의 크기를 N+1로 설정하고 초기화했다.

arr: 각 헛간과 연결된 헛간의 번호를 저장하는 이차원 리스트

visited: 방문된 헛간인지 아닌지를 구별하는 리스트

distance: 1번 헛간에서의 거리를 저장하는 리스트

arr = [[] for _ in range(N+1)]
visited = [False] * (N+1)
distance = [0] * (N+1)

 

사용자에게 헛간 번호 2개를 입력받는다.

모든 헛간은 양방향 길로 이어져 있다. ➡ 서로의 헛간 리스트에 상대 헛간 번호를 저장한다.

for _ in range(M):
    num1, num2 = map(int, input().split())
    arr[num1].append(num2)
    arr[num2].append(num1)

 

bfs를 호출한다.

1번 헛간부터 찾을 것이기 때문에 시작점인 1을 매개변수로 넘겨준다.

bfs(1) # 시작점

 

 

✔️ bfs 함수 내

 

해당 헛간과 연결되어 있는 모든 헛간들을 검사한다.

방문하지 않은 곳이라면 방문 처리를 한 후, 1번 헛간으로부터의 거리를 저장하고, q에 헛간 번호를 추가한다.

for i in arr[c]:
    if not visited[i]:
        visited[i] = True
        distance[i] = distance[c] + 1
        q.append(i)