백준 1260번 - DFS와 BFS (Python)

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

1260번: DFS와 BFS

 

생각해보기

• 인접 행렬과 인접 리스트의 구현과 탐색 방법
• 인접 행렬의 경우, 인수로 넘겨진 노드를 기준으로 해서 각각의 다른 노드들이 연결되어 있는지 확인하며 탐색
• 인접 리스트의 경우, 인수로 넘겨진 노드에 해당하는 인덱스에 연결된 노드의 정보들이 있음
• DFS와 BFS의 노드 탐색 순서

 

DFS

• 재귀 호출이나 스택으로 구현
• 함수 호출이 되면서 방문 체크

 

BFS

• 큐로 구현
• 함수에 넘겨진 인자를 큐에 삽입 후 방문 체크 → 시작 지점
• 방문하지 않은 노드를 탐색하며 방문 체크 후 큐에 삽입

 

풀이)

import sys
from collections import deque

sys.stdin = open('input.txt', 'r')

input = sys.stdin.readline

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

graph = [[] for _ in range(N + 1)]

# for _ in range(M) :

#     a, b = map(int, input().split())

#     graph[a].append(b)
#     graph[b].append(a)            # 양방향 그래프

# # 정점 번호가 작은 것을 먼저 방문하기 위해 정렬
# for node in graph :
#     node.sort()

matrix = [[0] * (N + 1) for _ in range(N + 1)]

visited = [0] * (N + 1)

for _ in range(M) :
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1 # 양방향 그래프


def DFS(k) :
    visited[k] = 1
    print(k, end = ' ')

    for i in range(1, N + 1) :
        if visited[i] == 0 and matrix[k][i] == 1 :
            DFS(i)

    # for i in graph[k] :
    #     if not visited[i] :
    #         DFS(i)


def BFS(k) :
    que = deque([k])
    visited[k] = 0

    while que :
        res = que.popleft()
        print(res, end = ' ')

        for i in range(1, N + 1) :
            if visited[i] == 1 and matrix[res][i] == 1 :
                que.append(i)
                visited[i] = 0

        # for i in graph[k] :
        #     if not visited[i] :
        #         que.append(i)
        #         visited[i] = True

DFS(V)

print()

BFS(V)

# 인접 행렬과 인접 리스트 각각의 장점과 단점