알고리즘 위클리 챌린지 [그래프 탐색1] 문풀

문제는 사진과 같으며,

답은,, 파이썬 기준으로 아래와 같으며 마지막 두줄을 추가하였다.

import sys
from collections import defaultdict, deque

input = sys.stdin.readline

N, M = map(int, input().split())

Graph = defaultdict(list)

for _ in range(M):
    s, e = map(int, input().split())
    Graph[s].append(e)   # 단방향

start = 1
Visited = [False] * (N + 1)
q = deque()

q.append(start)
Visited[start] = True

while q:
    current = q.popleft()
    print(current, end=" ")

    for next_node in Graph[current]:
        if not Visited[next_node]:
            Visited[next_node] = True
            q.append(next_node)

문제에 대한 요약은 다음과 같다.

정점의 개수: N

간선의 개수: M

간선 정보가 주어짐

• 단방향 그래프

BFS 알고리즘으로
정점 1번에서 시작해서
탐색되는 정점의 순서를 출력하라

문제에서 주어진 조건의 핵심 포인트는,

시작 정점은 항상 1

BFS (Queue 사용)

정답으로 방문 순서 출력

여기서 BFS는 = Breadth-First Search (너비 우선 탐색)을 의미한다.

그래프(또는 트리)에서
가까운 노드부터 차례대로 탐색하는 방법.

즉, 시작 정점에서 거리가 가까운 노드부터 먼저 방문하는 탐색 방법이다.
-> 따라서 이에 대한 주석 및 코드 해설은

# sys 모듈: 빠른 입력을 위해 사용
import sys

# defaultdict: 그래프를 쉽게 만들기 위해
# deque: BFS에서 사용할 큐 자료구조
from collections import defaultdict, deque

# input을 sys.stdin.readline으로 바꿔서 입력 속도 향상
input = sys.stdin.readline


# -----------------------------
# 1. 입력 받기
# -----------------------------

# N: 정점(노드)의 개수
# M: 간선의 개수
N, M = map(int, input().split())


# -----------------------------
# 2. 그래프 생성
# -----------------------------

# defaultdict(list):
# 존재하지 않는 key에 접근해도 자동으로 빈 리스트 생성
# → Graph[x].append(y) 할 때 KeyError 방지
Graph = defaultdict(list)

# 간선 정보를 입력받아 그래프에 저장
for _ in range(M):
    s, e = map(int, input().split())
    # s에서 e로 가는 단방향 간선
    Graph[s].append(e)

    # 만약 무방향 그래프라면 아래 줄도 추가해야 함
    # Graph[e].append(s)


# -----------------------------
# 3. BFS 초기 설정
# -----------------------------

# 문제에서 시작 정점은 항상 1번
start = 1

# 방문 여부를 저장하는 배열
# 인덱스를 정점 번호 그대로 쓰기 위해 N+1 크기
Visited = [False] * (N + 1)

# BFS에서 사용할 큐 (FIFO 구조)
q = deque()


# -----------------------------
# 4. 시작 정점 처리
# -----------------------------

# 시작 정점을 큐에 넣는다
q.append(start)

# 시작 정점은 방문 처리
# 큐에 넣을 때 방문 체크하는 것이 중요
Visited[start] = True


# -----------------------------
# 5. BFS 탐색 시작
# -----------------------------

# 큐가 빌 때까지 반복
while q:
    # 큐의 맨 앞에서 하나 꺼냄 (가장 먼저 들어온 노드)
    current = q.popleft()

    # 현재 방문한 노드를 출력
    # BFS 방문 순서 그대로 출력됨
    print(current, end=" ")

    # 현재 노드와 연결된 모든 이웃 노드 탐색
    for next_node in Graph[current]:

        # 아직 방문하지 않은 노드라면
        if not Visited[next_node]:

            # 방문 처리 (중복 방문 방지)
            Visited[next_node] = True

            # 큐에 넣어서 나중에 탐색
            q.append(next_node)

위와 같다.