[Python] 백준 6118번 문제, 숨바꼭질

<문제 링크>

 

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

6118번: 숨바꼭질

 

---

<풀이>

 

문제를 간단하게 해석하면 술래에게 잡히지 않기 위해 술래 위치를 기준으로 가장 멀리 있는 헛간이 어디냐라는 것이다.

그래서 결과 출력 형태로 [숨어야 하는 헛간 번호, 그 헛간까지의 거리, 그 헛간과 같은 거리를 갖는 헛간의 개수]를 공백을 두고 출력해야 한다.

술래와 가장 멀리 있는 헛간이 여러 개라면 그 중 가장 작은 방의 번호를 return하며, 여러 개의 방을 기억하기 위해 copy[]에 직전에 탐색한 노드 정보들을 저장시켰다.

또한, 헛간끼리 이어진 길은 양방향이기 때문에 visited[]를 통해 무한 루프 방지 및 탐색 수행을 맞친 노드를 구별해낸다.

 

BFS 수행 횟수는 count만큼이며, count를 구하기 위해 현재 탐색 중인 que[]와 다음 탐색 차례인 next_que[]를 사용했다.

현재 탐색 중인 노드와 인접한 노드들 중에서 방문한 적이 없다면, next_que[]에 삽입해 다음 차례를 기다린다.

 

que가 비었을 때, 현재 탐색이 끝난 것이므로, next_que가 비어 있지 않는 경우 꼭 next_que.copy()를 사용해 que에 삽입해준다. 아마도 리스트도 reference이기 때문에 que = next_que를 수행한다면, 다음 줄에 있을 next_que = []로 인해 que까지 []가 되버린다.

그렇기 때문에 next_que.copy()를 통해 깊은 복사를 수행해주어야한다.

 

BFS가 끝났다면 copy[]를 사용해 출력 형태에 맞춰 결과를 출력해주면 된다.

(! f"" 문법은 Python 최신 버전에서만 사용 가능하다. 겁나 편함 )

 

---

<코드>

N: 헛간의 개수(노드의 개수)

M: 헛간끼리 양방향으로 연결된 길의 수(간선 수)

room[]: 그래프 정보를 담고 있는 리스트

visited[]: 방문 여부를 체크하는 리스트

que[]: 현재 탐색 차례인 노드들

next_que[]: 다음 탐색 차례인 노드들

copy[]: 마지막 노드를 기억하기 위한 리스트

---

import sys

def bfs(room):
    que = [1] # 현재 노드들, 시작점은 1
    visited[1] = True
    next_que = [] # 다음 노드들
    copy = [] # 최종 큐 목록
    count = 0 # bfs 진행한 횟수

    while que:
        index = que.pop(0) # 현재 포커싱 노드 번호

        for value in room[index]: # 현재 포커싱 노드와 연결된 노드 목록 중에서
            if not visited[value]: # 방문 안 한 노드가 있다면
                visited[value] = True # 방문 체크 후
                next_que.append(value) # 다음 방문 예정에 추가

        if not que and next_que: # 현재 BFS(que)를 끝내고 다음 턴의 BFS(next_que)을 할 차례라면
            copy = next_que.copy() # 마지막 노드 목록 기록 -> 다음 턴의 BFS가 없다면 현재 if는 실행되지 않음
            que = next_que.copy()
            next_que = []
            count += 1

    return f"{min(copy)} {count} {len(copy)}"

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    room = [[] for _ in range(N+1)]
    visited = [False for _ in range(N+1)]

    # create room
    for i in range(M):
        A_i, B_i = map(int, sys.stdin.readline().rstrip().split())

        room[A_i].append(B_i)
        room[B_i].append(A_i)

    # result print
    print(bfs(room))