[baekjoon] 백준 6118번(파이썬): 숨바꼭질

문제

6118번: 숨바꼭질

- 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다.

- 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다.

- 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자.

- 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다.

- 모든 헛간은 M(1<= M <= 50,000)개의 양방향 길로 이어져 있고, 그 양 끝을 A_i 와 B_i(1<= A_i <= N; 1 <= B_i <= N; A_i != B_i)로 나타낸다.

- 또한 어떤 헛간에서 다른 헛간으로는 언제나 도달 가능하다고 생각해도 좋다. 

- 재서기는 발냄새가 지독하기 때문에 최대한 냄새가 안나게 숨을 장소를 찾고자 한다.

- 냄새는 1번 헛간에서의 거리(여기서 거리라 함은 지나야 하는 길의 최소 개수이다)가 멀어질수록 감소한다고 한다.

- 재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾을 수 있게 도와주자!

- 첫 번째는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러개면 가장 작은 헛간 번호를 출력한다), 두 번째는 그 헛간까지의 거리를, 세 번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야한다.

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 1번 헛간부터 탐색하며 방문 거리를 체크한다.

- 체크한 방문 거리를 통해 출력 예시를 수행한다.

코드

import sys
from collections import deque


# bfs 탐색
def bfs(v):
    queue = deque([v])
    visited[v] = 1

    while queue:

        target = queue.popleft()

        # 연결된 헛간을 확인
        for i in graph[target]:
            # 방문하지 않은 헛간이라면 방문
            if visited[i] == 0:
                # 방문 거리를 체크
                visited[i] = visited[target] + 1
                queue.append(i)


n, m = map(int, sys.stdin.readline().split())

# 노드 방문 여부와 순서 확인
visited = [0 for i in range(n + 1)]

# 각 연결된 노드를 표현
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# 1번 헛간부터 탐색
bfs(1)

# 최대 값의 인덱스 값 출력, 첫번째 헛간을 1로 두었기 때문에 최대값에서 1을 빼준 값을 출력, 최대 값의 개수 출력
print(visited.index(max(visited)), max(visited) - 1, visited.count(max(visited)))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법