오늘의 학습 키워드
BFS, Breadth-First Search(깊이 우선 탐색)
오늘의 문제
백준 18352번
https://www.acmicpc.net/problem/18352
문제 설명
입출력
BFS 탐색 순서
오름차순 방문: BFS 탐색 시 인접 정점들을 오름차순으로 방문.
- 시작 도시에서 BFS 탐색을 시작한다.
- 출발 도시 X에서 시작하여 BFS 탐색을 진행한다. 출발 도시는 큐에 넣고 방문 처리를 하며, 거리는 0으로 설정한다.
- 큐에서 노드를 추출하고 연결된 도시들을 탐색한다.
- 큐에서 현재 도시를 꺼내고, 이 도시와 연결된 인접 도시들을 탐색한다.
- 각 인접 도시가 방문되지 않은 경우에만 큐에 추가하고 방문 처리를 한다.
- 방문한 도시에 대해 현재까지의 최단 거리를 기록한다.
- 목표 거리 확인 및 결과 저장.
- 각 도시를 방문할 때마다 거리가 목표 거리 K와 같은 경우 해당 도시를 결과 리스트에 추가한다.
- 큐가 빌 때까지 반복하여 최단 거리를 찾는다.
- 큐가 빌 때까지 위 과정을 반복하며 목표 거리 K인 도시에 도달하는 모든 경우를 찾는다.
- 탐색이 끝난 후 결과를 출력한다.
- 목표 거리 K인 도시가 없다면 -1을 출력한다.
- 그렇지 않으면, 결과 리스트를 오름차순으로 정렬하여 출력한다.
BFS 탐색 순서 예시
-
시작 도시: 출발 도시 1에서 BFS 탐색을 시작한다. 시작 도시를 큐에 넣고 방문 처리를 하며, 거리는 0으로 설정한다.
-
첫 번째 단계: 큐에서 도시 1을 꺼내고, 이 도시와 연결된 인접 도시인 2와 3을 방문한다. 이 두 도시는 출발 도시 1과의 거리가 1이므로 큐에 추가하고 방문 처리를 한다.
-
두 번째 단계: 큐에서 도시 2를 꺼내고, 이 도시와 연결된 인접 도시인 4를 방문한다. 이때, 도시 4는 출발 도시 1과의 거리가 2가 된다. 도시 4를 큐에 추가하고 방문 처리를 한다.
-
목표 거리 확인: 큐에서 모든 도시를 탐색한 후, 거리가 정확히 2인 도시를 찾는다. 이 경우, 도시 4가 해당되므로 결과에 추가한다.
-
결과 출력: 결과 리스트에 있는 도시 번호를 오름차순으로 출력한다. 만약 거리가 k인 도시가 없다면 -1을 출력한다.
따라서 BFS 탐색 순서는 1 -> 2 -> 3 -> 4이며, 최단 거리가 2인 도시는 4번이다.
1. 기본 설정 및 입력 처리
from collections import deque
import sys
f = sys.stdin.readline
n, m, k, x = map(int, f().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
visited = [False] * (n+1)-
import sys와 from collections import deque: 빠른 입력과 BFS 탐색을 위해 필요한 라이브러리를 임포트한다. -
f = sys.stdin.readline: 입력 속도를 높이기 위해 표준 입력을 사용한다. -
n, m, k, x = map(int, f().split()): 도시의 개수 n, 도로의 개수 m, 목표 거리 k, 출발 도시 번호 x를 입력받는다. -
graph = [[] for _ in range(n+1)]: 각 도시 간의 단방향 도로를 인접 리스트로 표현하기 위한 그래프를 초기화한다. -
distance = [0] * (n+1): 각 도시의 최단 거리를 저장할 리스트를 초기화한다. -
visited = [False] * (n+1): 각 도시의 방문 여부를 기록하는 리스트를 초기화한다.
2. 그래프 구성
for _ in range(m):
a, b = map(int, f().split())
graph[a].append(b)-
for _ in range(m): m개의 도로 정보를 입력받아 그래프를 구성한다. -
a, b = map(int, f().split()): 도시 a에서 도시 b로 가는 단방향 도로가 존재한다는 의미이다. -
graph[a].append(b): 도시 a의 인접 리스트에 도시 b를 추가하여 단방향 도로를 표현한다.
3. BFS 탐색 정의 및 초기화
def bfs(start):
answer = []
q = deque([start])
visited[start] = True
distance[start] = 0-
def bfs(start): 출발 도시 start에서 BFS 탐색을 수행하는 함수이다. -
answer = []: 목표 거리가 k인 도시를 저장할 리스트이다. -
q = deque([start]): BFS 탐색을 위해 출발 도시를 큐에 넣는다. -
visited[start] = True: 출발 도시를 방문 처리한다. -
distance[start] = 0: 출발 도시의 거리는 0으로 설정한다.
4. BFS 탐색 과정
while q:
now = q.popleft()
for i in graph[now]:
if not visited[i]:
visited[i] = True
q.append(i)
distance[i] = distance[now] + 1
if distance[i] == k:
answer.append(i)-
while q: 큐가 빌 때까지 반복하여 BFS 탐색을 진행한다. -
now = q.popleft(): 큐에서 현재 도시를 꺼낸다. -
for i in graph[now]: 현재 도시와 연결된 모든 인접 도시를 탐색한다. -
if not visited[i]: 아직 방문하지 않은 도시라면 다음을 수행한다. -
visited[i] = True: 해당 도시를 방문 처리한다. -
q.append(i): 해당 도시를 큐에 추가한다. -
distance[i] = distance[now] + 1: 현재 도시로부터의 거리를 계산하여 저장한다. -
5. 결과 출력
if len(answer) == 0:
print(-1)
else:
answer.sort()
for i in answer:
print(i, end='\n')-
if len(answer) == 0: 만약 목표 거리가 k인 도시가 없다면 -1을 출력한다. -
else: 목표 거리가 k인 도시가 있는 경우, 이를 오름차순으로 정렬하여 출력한다.
전체 풀이
from collections import deque
import sys
f = sys.stdin.readline
n, m, k, x = map(int, f().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
visited = [False] * (n+1)
for _ in range(m):
a, b = map(int, f().split())
graph[a].append(b)
def bfs(start):
answer = []
q = deque([start])
visited[start] = True
distance[start] = 0
while q:
now = q.popleft()
for i in graph[now]:
if not visited[i]:
visited[i] = True
q.append(i)
distance[i] = distance[now] + 1
if distance[i] == k:
answer.append(i)
if len(answer) == 0:
print(-1)
else:
answer.sort()
for i in answer:
print(i, end='\n')
bfs(x)