[python] 1260번 - DFS와 BFS

문제

파이썬 풀이

이 문제는 기본적인 dfs, bfs를 구현하여 결과를 출력하는 문제이다.

우선 그래프는 인접 행렬 방식으로 구현을 하였다.

각종 변수 초기화

n, m, v = map(int, input().rstrip().split())
graph = [[0]*(n+1) for _ in range(n+1)]

visited_bfs = [0] * (n+1)
visited_dfs = [0] * (n+1)

graph에서 n+1을 한 이유는 인덱스는 0부터 시작이어서 1부터 시작하는 숫자와 인덱스를 매칭 시키기 위해 1개를 더 생성한 것이다.

visited배열들은 해당 인덱스에 해당하는 숫자를 방문했는지 여부를 기록할 리스트이다. (방문 x : 0, 방문 o : 1)

즉 예를 들어 2라는 숫자의 노드를 방문했다면 visited리스트에서 인덱스 2에 해당하는 값을 1로 바꿔준다.

그래프 입력 받기

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

방향이 없는 무방향 그래프이므로 (a, b), (b, a)에 모두 연결이 되어있다고 값을 1로 저장해준다.

dfs와 bfs

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 : #방문 기록이 없고 v와 인접하다면
            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

dfs의 경우 for문을 통해 1부터 n까지 반복하면서 i인덱스에 대해 방문 기록이 없고, v와 인접하다면 dfs(i)를 해주는 재귀적인 방법으로 구현을 하였다.

 

bfs의 경우 재귀적으로 동작하지 않는다. deque자료 구조를 이용했다.

반복문을 통해 1부터 n까지를 반복하는데 i인덱스 값에 대해 방문 기록이 없고, v와 인접해있다면, i를 큐에 넣고, i를 방문했다고 표시해준다. v는 큐에서 꺼낸 값이다.

 

전체 코드

import sys
input = sys.stdin.readline
from collections import deque

n, m, v = map(int, input().rstrip().split())
graph = [[0]*(n+1) for _ in range(n+1)]

visited_bfs = [0] * (n+1)
visited_dfs = [0] * (n+1)

# 그래프 입력 받기
for _ in range(m) :
    a, b = map(int, input().rstrip().split())
    graph[a][b] = graph[b][a] = 1


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 : #방문 기록이 없고 v와 인접하다면
            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

dfs(v)
print()
bfs(v)