BOJ 6118번 숨바꼭질

BOJ 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번 헛간에서의 거리(여기서 거리라 함은 지나야 하는 길의 최소 개수이다)가 멀어질수록 감소한다고 한다. 재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾을 수 있게 도와주자!

입력

첫 번째 줄에는 N과 M이 공백을 사이에 두고 주어진다.

이후 M줄에 걸쳐서 A_i와 B_i가 공백을 사이에 두고 주어진다.

출력

출력은 한줄로 이루어지며, 세 개의 값을 공백으로 구분지어 출력해야한다.

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

거리를 찾는다는 점에서 DFS보다 BFS가 더 적합하다는 것에는 이견이 없었다.

다만, 왠지 Queue를 사용하지 않고도 BFS를 구현할 수 있을 것 같아서, for문 두개를 엮어서 인접행렬을 도는 코드를 작성했다. 예제 TC는 통과했지만 제출하면 4%에서 ‘틀렸습니다’가 떴다.

생각해보니 내가 작성한대로 반복문을 돌리면, BFS의 취지와는 다르게, for문에서 index를 하나씩 더해가며 순서대로 방문하게 된다.

결론적으로, queue랑 사용원리는 매우 비슷하게 구현이 되었는데, 방문 안한곳은 frontier라는 배열에 넣어두고, while문안에서 계속 돌린다. queue를 사용할때랑 마찬가지로 frontier라는 배열이 빌 때까지.

BFS Queue 사용

from collections import deque
N,M = map(int,input().split())

S = [[] for _ in range(N+1)]
dist = [0] * (N+1)

for i in range(M):
    a,b = map(int,input().split())
    S[a].append(b)
    S[b].append(a)

def bfs():
    global dist
    queue = deque()
    queue.append(1)
    dist[1]=1

    while queue:
        node = queue.popleft()
        for n in S[node]:
            if dist[n] ==0:
                dist[n] = dist[node]+1
                queue.append(n)
    return
bfs()

maxv = max(dist)

print(dist.index(maxv),maxv-1,dist.count(maxv))

BFS Queue 사용 ❌

from collections import deque
N,M = map(int,input().split())

S = [[] for _ in range(N+1)]
dist = [0] * (N+1)

for i in range(M):
    a,b = map(int,input().split())
    S[a].append(b)
    S[b].append(a)

def bfs():
    global dist
    node = 1
    dist[node]=1
    frontier = [node]
    while frontier:
        next_frontier = []
        for i in frontier:
            for j in S[i]:
                if dist[j] ==0:
                    dist[j] = dist[i]+1
                    next_frontier.append(j)
        frontier = next_frontier
    return

bfs()

maxv = max(dist)

print(dist.index(maxv),maxv-1,dist.count(maxv))

queue를 사용하지 않는 bfs 참고 링크

https://gist.github.com/dpapathanasiou/21d3d9b4fcad562dd048d51742340955