[1260번] DFS와 BFS Python🐍

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

1260번: DFS와 BFS

알고리즘 [접근 방법]

dfs는 깊이 우선 탐색, 즉 말 그대로 깊이를 우선적으로 탐색해주는 것이고,
bfs는 너비 우선 탐색, 즉 너비를 우선적으로 탐색해주는 것이다.

문제 자체는 bfs의기본 구조를 벗어나지 않아 쉽게 풀 수 있지만 주의해야할 점은 dfs와 bfs를 각자 실행해야하므로 visited 를 초기화 해주거나, 두개 만들거나, dfs는 visited를 True bfs 는 False로 해주는 등 처리를 해주어야한다.

 

DFS와 BFS를 구현하기 위해서 트리나 그래프의 구조를 가지고 있어야 서로 연결된 노드들을 파악이 가능하다. 하지만 해당 문제에서 Class Node를 하면서 Node를 만들고 연결해서 문제를 해결하기에는 무리가 있다. 따라서 인접행렬 방식으로 행과 열을 통해서 값을 해당 숫자들이 연결되어 있는지 확인하는 방법으로 진행한다.

N개의 숫자가 있으므로 N+1 x N+1의 행렬을 리스트를 통해서 만들고 0으로 채워준다. 인덱스와 값을 일치시키기 위해서 N+1개의 숫자를 사용한다.

연결된 숫자들 값을 입력받아서 해당 행과 열의 값을 1로 바꿔준다. 이를 통해서 행의 숫자와 열의 숫자가 연결되어 있다는 표시를 해준다.

풀이

1.  먼저 입력 변수로 n,m,v를 입력 받는다
2.  인접 영행렬을 생성시켜준다. (=graph)
3.  방문할 곳을 체크할 visited 리스트를 DFS, BFS로 나누어 2개를 만들어준다.
4.  입력 받는 두 값에 대해 영행렬에 1을 삽입한다.
5.  DFS를 구현할 때, 정점 V에 대한 visited 값에 1을 넣어 방문을 표시하고 그후, 출력한다. 
6.  DFS) for 문의 범위가 1부터 n+1까지 돌면서 visited 미방문 & graph에 대한 v,i가 1일때만 dfs를 재귀실행
7.  BFS를  구현할 때도 마찬가지로 visited 값에 1을 넣어 방문을 표시하고 queue에 값을 넣으면서 출력한다.
8.  BFS) for을 돌면서 똑같이 visited 미방문 & graph에 대한 v,i가 1일 때 queue에 삽입을 진행하고 방문을 표시한다.

 

코드

import sys
from collections import deque
def dfs(v):
    visited_dfs[v] = 1
    print(v, end = " ")
    for i in range(1, n+1):
        if visited_dfs[i] == 0 and graph[v][i] == 1:
            dfs(i)

def bfs(v):
    q = deque()
    q.append(v)
    visited_bfs[v] = 1
    while q:
        v = q.popleft()
        print(v, end=" ")
        for i in range(1, n+1):
            if visited_bfs[i] == 0 and graph[v][i] == 1:
                q.append(i)
                visited_bfs[i] = 1


read = sys.stdin.readline
n, m, v = map(int, read().split())

graph = [[0] * (n+1) for i in range(n+1)]
visited_bfs =  [0] * (n+1)
visited_dfs = [0] * (n+1)

for _ in range(m):
    a, b = map(int, read().split())
    graph[a][b] = graph[b][a] = 1


dfs(v)
print()
bfs(v)