[python] 백준 1260 번 DFS와 BFS

백준 1260 번 DFS와 BFS

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

문제

풀이

여기서의 하이라이트는 간선리스트를 인접리스트로 변환하는 것.
for v1, v2 in edge_list:
graph[v1].append(v2)
graph[v2].append(v1)

from collections import deque

n, m, v = map(int, input().split())
edge_list = []
for _ in range(m):
    v1, v2 = map(int, input().split())
    edge_list.append([v1, v2])

# 인접 리스트 초기화
graph = [[] for _ in range(n + 1)]

# 간선을 인접 리스트에 추가
for v1, v2 in edge_list:
    graph[v1].append(v2)
    graph[v2].append(v1)  # 무방향 그래프이므로 양쪽에 추가

def dfs(visited, v, graph):
    visited[v] = True
    print(v, end=' ')
    for i in sorted(graph[v]):
        if not visited[i]:
            dfs(visited, i, graph)

def bfs(visited, start, graph):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in sorted(graph[v]):
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# DFS 수행
visited = [False] * (n + 1)
dfs(visited, v, graph)
print()  # 줄바꿈

# BFS 수행
visited = [False] * (n + 1)
bfs(visited, v, graph)

📌 주의

• dfs 부르고 bfs 부를 때 visited 초기화 해주기
• 그리고 sorted! 중요하다. 인접리스트로 바꾸다 보니 리스트의 정렬이 오름차순이 되어있지 않아서 결과값이 다르게 나오는 상황 발생. for 문 돌릴 때 for i in sorted(graph[v]) 꼭 sorted 써주기
• 참고로 줄바꿈은 print() 그리고 end = ' ' 는 한 칸 띄고 출력하기