백준 1260번 DFS와 BFS 파이썬 (python code)

난이도: 실버2
번호:9633번

 

그래프의 DFS BFS탐색에 관한 문제이다.

DFS와 BFS의 정의를 알고 구현할 수 있으면 쉽게 풀 수 있는데

bfs를 처음 풀어봐서 왜 queue를 이용해야 하는지 몰라서 오래걸렸다.

 

from sys import stdin
import time as t

s=t.time()


def dfs(node):
    print(node, end=' ')
    visitdfs[node] = 1
    for i in range(1,N+1):
        if visitdfs[i] == 0 and matrixmap[node][i] == 1:
            dfs(i)


def bfs(node):
    tovisit =[node]
    visitbfs[node]=1
    while tovisit:
        node=tovisit[0]
        print(tovisit.pop(0), end=' ')
        for i in range(1,N+1):
            if visitbfs[i] == 0 and matrixmap[node][i] == 1:
                tovisit.append(i)
                visitbfs[i] = 1



if __name__ == '__main__':
    N,M,S = map(int,stdin.readline().split())
    matrixmap = [[0] * (N+1) for i in range(N+1)]
    visitdfs = [0] * (N+1)
    visitbfs = [0] * (N+1)

    for i in range(M):
        x,y=map(int, stdin.readline().split())
        matrixmap[x][y]=matrixmap[y][x]=1
    dfs(S)
    print()
    bfs(S)