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

문제 접근

최종 목표: DFS와 DFS 탐색

문제에서 입력으로 주어지는 간선은 양방향이라고 언급하였으므로, 인접 리스트가 아닌 인접 행렬을 이용해 문제를 풀어야 한다.

문제 해결 아이디어

enumerate() 함수를 이용하면 간단하게 인접 행렬을 사용할 수 있다.

코드

from collections import deque
n, m, v = map(int, input().split())

visited = [False] * (n+1)
graph = [[0] * (n+1) for _ in range(n+1)]

# 인접 행렬 입력
for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1 
    graph[b][a] = 1

def dfs(graph, start, visited):
    # 현재 방문 노드 처리
    visited[start] = True
    print(start, end=' ')
    # 인접 노드 탐색
    for next_node, value in enumerate(graph[start]):
        if value == 1:
            if not visited[next_node]:
                dfs(graph, next_node, visited)    

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        # 방문 노드 처리
        now = queue.popleft()
        print(now, end=' ')
        # 인접 노드 탐색
        for next_node, value in enumerate(graph[now]):
            if value == 1:
                if not visited[next_node]:
                    queue.append(next_node)
                    visited[next_node] = True

dfs(graph, v, visited)
print()
visited = [False] * (n+1)
bfs(graph, v, visited)