큐(queue), BFS(너비 우선 탐색), 트리의 지름, 백준 1167 파이썬

1. 큐(queue)

개요

삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조

파이썬 구현 방법

collections에 deque 사용하여 간단하게 구현 가능

from collections import deque

q = deque()

• 연산(이름이 q일 때)
  • q.append(data): rear 부분에 새로운 데이터를 삽입하는 연산
  • q.popleft(): front 부분에 있는 데이터를 삭제하고 확인하는 연산
  • s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산

 

2. 너비 우선 탐색(BFS, breadth-first search)

개요

그래프 완전 탐색 방법 중 하나.

시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘.

시간 복잡도(노드 수: V, 에지 수: E): O(V + E)

 

선입 선출(FIFO)방식으로 탐색하므로 큐를 이용해 구현.

탐색 시작 노드와 가장 가까운 노드를 먼저 방문하면서 탐색하므로 목표 노드에 도착하는 최단 경로 횟수 보장

구현 방법

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   1. 원본 그래프를 인접 리스트로 그래프 표현하기
   2. 방문 리스트 초기화하기
   3. 시작 노드를 큐에 삽입하기
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
   1. 큐에서 노드를 꺼내기
   2. 꺼낸 노드를 탐색 순서에 기입
   3. 인접 리스트의 인접 노드를 스택에 삽입하며 방문 여부 리스트에 표시
3. 큐 자료구조에 값이 없을 때까지 반복
   1. 이미 다녀간 노드를 가지 않으면서 반복

 

3. 트리의 지름

개요

트리 내 가장 거리가 먼 두 노드사이의 거리

구현 방법

임의의 노드에서 BFS를 사용하여 가장 거리가 먼 노드를 구한 뒤

해당 지점에서 초기화 후 다시 BFS를 돌며 가장 거리가 먼 곳을 확인하면 그때의 길이가 트리의 지름

 

4. 백준 문제

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

1167번: 트리의 지름

import sys

input = sys.stdin.readline
from collections import deque

N = int(input())

v_list = [-1] * (N + 1)  # 방문 리스트 초기화
n_list = [[] for i in range((N + 1))]  # 인접 리스트 초기화
for i in range(N):
    e_list = list(map(int, input().split()))
    for j in range(1, len(e_list) - 1, 2):
        n_list[e_list[0]].append((e_list[j], e_list[j + 1]))

def bfs(src):		# BFS 구현
    queue = deque()
    queue.append(src)       # 큐에 시작 노드 넣고 방문처리
    v_list[src] = 0
    while queue:            # 큐가 빌 때까지, 방문하여 관련 작업 처리
        cur = queue.popleft()
        for edge in n_list[cur]:
            # 방문하지 않았다면 길이 추가하고 큐에 추가
            # 트리이기 때문에 사이클 x -> 각 노드에 방문할 때 길이가 유일한 경로
            if -1 == v_list[edge[0]]:
                v_list[edge[0]] = v_list[cur] + edge[1]
                queue.append(edge[0])


bfs(1)
max_node = v_list.index(max(v_list))     # 첫 번째 순회 후 가장 거리가 먼 노드를 저장

v_list = [-1] * (N + 1)                  # 새로운 방문 리스트
bfs(max_node)

print(max(v_list))