(백준 알고리즘 문제풀이) 1260번 BFS, DFS

문제

 

문제 링크

 

문제 접근

• DFS
  - 모든 노드를 방문하고 싶을 때 사용한다.
  - Root node를 시작으로 다음 분기까지 넘어가기 전에 완전히 탐색하는 것!!
  - 한 방향으로 계속 탐색을 하다가 더 이상 탐색할 수 없을 때, 갈림길로 돌아와 완전히 탐색한다.
  - 어떤 노드를 방문했었는지 여부를 반드시 확인해야한다.
• BFS
  - Root node를 시작해서 인접한 노드를 먼저 탐색하는 방법
  - 시작점에서 가장 가까운 점을 먼저 방문한다 -> 최단 경로나 임의의 경로를 찾고 싶을 때 사용한다
  - 재귀적으로 동작하지 않으며, queue를 이용하여 반복적 형태로 구현한다.

 

코드

import sys
from collections import deque

# N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점의 번호
N, M, V = map(int, sys.stdin.readline().split())
# 0번 인덱스는 무시하기 위해서 N이 아닌 N+1 이용

# 탐색했는지 여부를 판단하기 위해서 check list를 활용
# DFS check list
checked = [0] * (N + 1)
# BFS check list
checked2 = [0] * (N + 1)

# 입력받는 그래프 만들기
graph = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(M):
    x, y = map(int, sys.stdin.readline().split())
    graph[x][y] = 1
    graph[y][x] = 1
# print(graph)
# for i in graph:
#     print(i)


# DFS 기능 구현 
def dfs(V):
    # print(checked)
    checked[V] = 1
    print(V, end=" ")

    for i in range(1, N+1):
        if checked[i] == 0 and graph[V][i] == 1:
            dfs(i)


# BFS 기능 구현
def bfs(V):
    q = deque()
    q.append(V)
    checked2[V] = 1

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

        for i in range(1, N+1):
            if checked2[i] == 0 and graph[V][i] == 1:
                q.append(i)
                checked2[i] = 1


# 실행
dfs(V)
print("")
bfs(V)

느낀점

기초적인 알고리즘 (깊이 우선 탐색, 너비 우선 탐색)이지만 기초적인 것에 대한 개념을 복습하는 것이 중요하다는 것을 깨달을 수 있었다. 그리고 다양한 코딩 문제를 풀기 위해서는 아주 중요한 알고리즘이라고 생각한다.