05-2 너비 우선 탐색
- 너비 우선 탐색 BFS도 그래프를 완전 탐색하는 방법이다.
- 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
- 기능: 그래프 완전 탐색
- 특징: FIFO 탐색, Queue 자료구조 이용
- 시간 복잡도(노드 수 V, 에지 수 E): O(V+E)
- 너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다.
- 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.
[너비 우선 탐색의 핵심 이론]
- BFS를 시작할 노드를 정한 후 자료구조 초기화하기
- DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 리스트가 필요하다.
- 그래프를 인접 리스트로 표현하는 것 역시 DFS와 동일하다.
- 하나 차이가 있다면 스택이 아닌 큐를 사용한다.
- 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
- 큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다.
- 이때, 방문 리스트를 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다.
- 큐에서 꺼낸 노드는 탐색 순서에 기록한다.
- 큐 자료구조에 값이 없을 때까지 반복하기
- 큐에 노드가 없을 때까지 앞선 과정을 반복한다.
- 선입선출 방식으로 탐색하므로 탐색 순서가 DFS와 다름을 확인해 보자.
📌 문제 026) DFS와 BFS 프로그램
시간 제한 2초, 실버 II, 백준 1260번
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
4 5 1 # 노드 개수, 에지 개수, 시작점 1 2 1 3 1 4 2 4 3 4
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
1 2 4 3 1 2 3 4
1단계 문제 분석
- 인접 리스트에 그래프를 저장한다
- DFS를 실행하면서 방문 리스트 체크와 탐색 노드 기록을 수행한다.
- 작은 번호 노드부터 탐색하므로 인접 노드를 오름차순으로 정렬한 후 재귀 함수를 호출하자.
- BFS도 같은 방식으로 진행한다. 노드를 오름차순 정렬하여 큐에 삽입한다.
- DFS와 BFS를 마쳤다면 각각 탐색하며 기록한 데이터를 출력한다.
2단계 슈도 코드
N(노드 개수) M(에지 개수) Start(시작점)
A(그래프 데이터 저장 인접 리스트)
for M의 개수만큼 반복:
A 인접 리스트에 그래프 데이터 저장
# 방문할 수 있는 노드가 여러 개일 경우에는 번호가 작은 것을 먼저 방문하기 위해 정렬
for N+1의 개수만큼 반복:
각 노드와 관련된 에지를 정렬
# DFS 구현하기
DFS:
현재 노드 출력하기
visited 리스트에 현재 노드 방문 기록하기
현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행하기(재귀 함수 형태)
visited 리스트 초기화
DFS(Start) 실행
# BFS 구현하기
BFS:
큐 자료구조에 시작 노드 삽입
visited 리스트에 현재 노드 방문 기록
while 큐가 비어 있을 때까지:
큐에서 노드 데이터를 가져오기
가져온 노드 출력
현재 노드의 연결 노드 중 미 방문 노드를 큐에 삽입(append 연산)하고 방문 리스트에 기록
visited 리스트 초기화
BFS(Start) 실행3단계 코드 구현
from collections import deque
N, M, Start = map(int, input().split())
A = [[] for _ in range(N+1)]
for _ in range(M):
s, e = map(int, input().split())
A[s].append(e) # 양방향 에지이므로 양쪽에 에지를 더하기
A[e].append(s)
for i in range(N+1):
A[i].sort() # 번호가 작은 노드부터 방문하기 위해 정렬하기
def DFS(v):
print(v, end=' ')
visited[v] = True
for i in A[v]:
if not visited[i]:
DFS(i)
visited = [False] * (N+1)
DFS(Start)
def BFS(v):
queue = deque()
queue.append(v)
visited[v] = True
while queue:
now_Node = queue.popleft()
print(now_Node, end=' ')
for i in A[now_Node]:
if not visited[i]:
visited[i] = True
queue.append(i)
print()
visited = [False] * (N+1) # 리스트 초기화
BFS(Start)📌 문제 027) 미로 탐색하기
시간 제한 1초, 실버 I, 백준 2178번
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
4 6 # N, M 101111 101010 101011 111011
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
15
1단계 문제 분석
- N, M의 최대 데이터의 크기가 100으로 매우 작기 때문에, 시간 제한은 별도로 생각하지 않아도 되는 문제이다.
- 문제의 요구사항은 지나야 하는 칸 수의 최솟값을 찾는 것이다.
- 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지를 구하는 것과 동일하다.
- BFS를 사용해 최초로 도달했을 때 깊이를 출력하면 문제를 해결할 수 있다.
- DFS보다 BFS가 적합한 이유는 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후, 다음 깊이로 넘어가기 때문이다.
- 2차원 리스트에 데이터를 저장한 다음 (1, 1)에서 BFS를 실행한다.
- 상, 하, 좌, 우 네 방향을 보며 인접한 칸을 본다. 인접한 칸의 숫자가 1이면서 아직 방문하지 않았다면 큐에 삽입한다.
- 종료 지점 (N, M)에서 BFS를 종료하며 깊이를 출력한다.
- 현재는 하, 우만 방문할 수 있으므로 하, 우 순서로 노드를 큐에 삽입한다.
- 이때 방문된 데이터의 값을 depth의 값으로 저장하기 위해 이전 데이터의 값 +1로 업데이트한다.
- 이런 방식으로 노드를 방문하면 깊이 9단계에서 (4, 6)에 도달한다.
2단계 슈도 코드
dx, dy(상하좌우를 탐색하기 위한 define 값 정의 변수)
N(row), M(column)
A(데이터 저장 2차원 행렬)
visited(방문 기록 저장 리스트)
for N만큼 반복:
for M만큼 반복:
A 리스트에 데이터 저장
# BFS 구현하기
BFS:
큐에 시작 노드 삽입
visited 리스트에 현재 노드 방문 기록
while 큐가 비어 있을 때까지:
큐에서 노드 데이터를 가져오기
for 상하좌우 탐색:
if 유효한 좌표:
if 이동할 수 있는 칸이면서 방문하지 않은 노드:
visited 리스트에 방문 기록
A 리스트에 depth를 현재 노드의 depth + 1로 업데이트
큐에 데이터 삽입
BFS(0, 0) 실행
A[N-1][M-1]3단계 코드 구현
from collections import deque
# 상하좌우를 탐색하기 위한 리스트 선언
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
N, M = map(int, input().split())
A = [[0] * M for _ in range(N)]
visited = [[False] * M for _ in range(N)]
for i in range(N):
numbers = list(input())
for j in range(M):
A[i][j] = int(numbers[j])
def BFS(i, j):
queue = deque()
queue.append((i, j))
visited[i][j] = True
while queue:
now = queue.popleft()
for k in range(4):
x = now[0] + dx[k]
y = now[1] + dy[k]
if x >= 0 and y >= 0 and x < N and y < M: # 좌표 유효성 검사
if A[x][y] != 0 and not visited[x][y]:
visited[x][y] = True
A[x][y] = A[now[0]][now[1]] + 1
queue.append((x, y))
BFS(0, 0)
print(A[N-1][M-1])📌 문제 028) 트리의 지름 구하기
시간 제한 2초, 골드 III, 백준 1167번
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
입력
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.
먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.5 # 노드 개수 1 3 2 -1 2 4 4 -1 3 1 2 4 3 -1 4 2 4 3 3 5 6 -1 5 4 6 -1
출력
첫째 줄에 트리의 지름을 출력한다.
11
1단계 문제 분석
[가장 긴 경로 찾기 아이디어]
- 임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나이다.
- 그래프를 인접 리스트로 저장한다.
- (노드, 가중치)를 표현하기 위해 튜플로 선언한다.
- 임의의 노드에서 BFS를 수행하고 탐색할 때, 각 노드의 거리를 리스트에 저장한다.
- 2번 과정에서 얻은 리스트에서 임의의 노드와 가장 먼 노드를 찾는다. 그리고 다시 그 노드부터 BFS를 다시 수행한다.
- 3번 과정에서 거리 리스트에 저장한 값 중 가장 큰 값을 이 트리의 지름으로 출력한다.
2단계 슈도 코드
N(노드 개수)
A(그래프 데이터 저장 인접 리스트)
for N만큼 반복:
A 인접 리스트에 그래프 데이터 저장
visited 리스트 초기화
distance 리스트 초기화
# BFS 구현
BFS:
큐 자료구조에 시작 노드 삽입
visited 리스트에 현재 노드 방문 기록
while 큐가 비어 있을 때까지:
큐에서 노드 데이터를 가져오기
for 현재 노드의 연결 노드:
if 미 방문 노드:
큐에 데이터 삽입
visited 리스트에 방문 기록
큐에 삽입 된 노드 거리 = 현재 노드의 거리 + 에지의 가중치로 변경
BFS(임의의 점을 시작점으로) 실행
distance 리스트에서 가장 큰 값을 지닌 노드를 시작점으로 지정
visited 리스트 초기화
distance 리스트 초기화
BFS(새로운 시작점으로) 실행
distance 리스트에서 가장 큰 수를 정답으로 출력3단계 코드 구현
from collections import deque
N = int(input())
A = [[] for _ in range(N+1)]
for _ in range(N): # A 인접 리스트에 그래프 데이터 저장
Data = list(map(int, input().split()))
index = 0
S = Data[index]
index += 1
while True:
E = Data[index]
if E == -1:
break
V = Data[index + 1]
A[S].append((E, V))
index += 2 # -1 이 되면서 while 루프 종료
distance = [0] * (N+1)
visited = [False] * (N+1)
def BFS(v):
queue = deque()
queue.append(v)
visited[v] = True
while queue:
now_Node = queue.popleft()
for i in A[now_Node]:
if not visited[i[0]]:
visited[i[0]] = True
queue.append(i[0])
distance[i[0]] = distance[now_Node] + i[1] # 거리 리스트 업데이트
BFS(1)
Max = 1
for i in range(2, N+1):
if distance[Max] < distance[i]:
Max = i
distance = [0] * (N+1)
visited = [False] * (N+1)
BFS(Max)
distance.sort()
print(distance[N])
안녕하세요 :)