[백준/파이썬] 1260 DFS와 BFS

#문제링크

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

1260번: DFS와 BFS

#나의풀이

import sys
from collections import deque

def DFS(number):
    print(number, end=' ')
    ch[number] = 1
    for i in range(1, n+1):
        if board[number][i] == 1 and ch[i] == 0:
            DFS(i)

def BFS(number):
    Q = deque([number])
    ch[number] = 1
    while Q:
        tmp = Q.popleft()
        print(tmp, end=' ')
        for i in range(1, n+1):
            if board[tmp][i] == 1 and ch[i] == 0:
                Q.append(i)
                ch[i] = 1

if __name__ == '__main__':
    n, m, v = map(int, sys.stdin.readline().split())
    board = [[0] * (n+1) for _ in range(n+1)]
    ch = [0] * (n+1)

    for _ in range(m):
        s, e = map(int, sys.stdin.readline().split())
        board[s][e] = 1
        board[e][s] = 1

    DFS(v)
    ch = [0] * (n+1)
    print()
    BFS(v)

#해설

DFS와 BFS로 그래프를 방문하여 방문한 순서대로 출력하는 문제

방문했는지 여부를 확인하기 위해 체크배열(ch)를 만들어서 방문했을시 값을 1로 바꾸고 각 조건문에 0이 아닐시 다시 방문하지 않도록 설정했다.

DFS는 깊이우선탐색으로 조건문에 일치하는 값이 나온다면 바로 재귀로 다시 넘어간다.

예를들어 N까지의 수가 있다고 했을때 1을 방문했을때 반복문을 돌면서 1~N까지 도는데 2에서 조건문이 일치했을경우 다시 2를 방문해서 1~N까지 돌게된다. 반면에 BFS는 넓이우선탐색으로 1을 방문하고 1~N까지 전체를 검사해 순서대로 방문할 값을 저장해놓고 하나씩 꺼내어 방문하는데 이후 조건에 일치하더라도 기본에 저장된곳에 마지막에 값을 추가시켜 나중에 방문하게 된다.