[백준/Python] 1260번 DFS와 BFS

---

문제

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

---

개념 이해

오늘은 미루고 미뤄왔던 DFS와 BFS의 개념을 정리하며 문제를 풀어보려 한다.

학부 과정중에 잠깐 배웠던 적이 있는데 다 까먹어버렸다..

 

용어정리

• 정점 / 노드 : 특정 위치
• 간선 : 위치 간의 관계, 정점(노드)을 연결한 선

 

DFS

DFS란? 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

재귀 함수 또는 스택을 이용해 알고리즘을 구현한다.

 

BFS

BFS란? 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

큐를 이용해 알고리즘을 구현한다.

---

문제풀이(정답)

n, m, v = map(int, input().split())

# 행렬 만들기

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

for _ in range(m):

    x, y = map(int, input().split())

    graph[x][y] = graph[y][x] = 1       # 정점이 연결되어 있으면 1

# 방문 리스트 만들기

visited1 = [0] * (n+1)       # dfs

visited2 = [0] * (n+1)       # bfs

def dfs(v):

    visited1[v] = 1      # 시작 노드 방문 표시

    print(v, end=' ')

    for i in range(1, n+1):

        if graph[v][i] == 1 and visited1[i] == 0: # 노드가 연결되어 있고 방문한 적이 없다

            dfs(i)

dfs(v)

print() # 들여쓰기

def bfs(v):

    queue = [v]

    visited2[v] = 1

    while queue:

        v = queue.pop(0)    # 방문 노드 제거

        print(v, end=' ')

        for i in range(1, n+1):

            if graph[v][i] == 1 and visited2[i] == 0:

                queue.append(i)    # 큐에 i를 삽입

                visited2[i] = 1    # 방문처리

bfs(v)

 

먼저 graph변수에 (n+1)X(n+1) 행렬을 만들어 연결된 노드들에 대해 1을 할당해 주었다.

그리고 DFS와 BFS에 각각 방문 리스트를 만들어 주었다. 노드가 방문했으면 1 그렇지 않으면 0으로 표기했다.

 

그리고 DFS를 구하는 함수를 작성했다.

 

1. 현재 노드 v를 방문했다고 표시 (visited1[v] = 1)
2. 방문한 노드를 출력 (print(v, end=' '))
3. 1번 노드부터 n번 노드까지 순회하면서,
   • 현재 노드 v와 연결된 노드 i를 찾고 (graph[v][i] == 1)
   • 방문하지 않은 경우 (visited1[i] == 0), 해당 노드에서 다시 dfs(i) 호출

 

 

 

그 후, BFS를 구하는 함수를 작성했다.

 

1. 시작 노드를 큐에 넣고 방문 처리 (queue = [v], visited2[v] = 1)
2. 큐에서 노드를 꺼내 출력 (print(v, end=' '))
3. 1번 노드부터 n번 노드까지 탐색하며,
   • 현재 노드 v와 연결된 i를 찾고 (graph[v][i] == 1)
   • 방문하지 않았다면 (visited2[i] == 0),
     • queue.append(i) (큐에 삽입)
     • visited2[i] = 1 (방문 체크)
4. 큐가 빌 때까지 위 과정을 반복

내일은 DFS와 BFS의 개념을 알았으니 관련 문제를 풀어봐야겠다.