[Python] 백준 알고리즘 1260번: DFS와 BFS

이번에 푸는 문제는 백준 알고리즘 1260번: DFS와 BFS로 난이도는 Siver 2 에 해당한다.

문제는 다음과 같다.

이문제는 기본적인 BFS/DFS 개념을 코드로 구현한 문제로,

예제 입력과 출력만 잘 맞추어서 넣어주면 된다.

 

DFS의 경우, Depth를 타고 들어가면서 탐색하므로 재귀를 쓰게되고,

BFS의 경우, 같은 Depth끼리 보면서 탐색하므로 queue를 활용하게된다.

 

나동빈님 블로그에서 자세한 개념을 볼 수 있다.(책으로 이전에 공부했었고, 다시 복습하면서 참고했음)

15. 너비 우선 탐색(BFS)

 

# 작성자 : SH_WON_96
# 2020-09-06
# 2020-12-29 review
# 알고리즘 - Graph
# 문제번호 : 1260

# 초기 입력값 받기

import sys
import math
input = sys.stdin.readline

N,M,V = map(int, input().split(" "))

# Input받을 Graph (N+1)X(N+1)로 만들기
G = [[0 for i in range(N+1)] for j in range(N+1)]


# M개의 간선, 연결있으면 1로 변경
for i in range(M):
    x,y = map(int,input().split(" "))
    # 대칭이니깐 양쪽 다 써줌
    G[x][y] = 1
    G[y][x] = 1


def BFS(G,s):
    queue = [] # queue는 내가 방문해야할 노드 모음
    Visit = [] # Visit은 내가 방문한 노드 모음
    queue.append(s)
    Visit.append(s)
    while(len(queue)!=0):
    	# queue에서 앞에서 하나씩 꺼내서 아랫층(?) 탐색
        poped = queue.pop(0)
        for i in range(1,N+1):
        	# 방문해야할 노드들을 순차적으로 queue 뒷쪽으로 넣고, 방문한 것으로 처리
            if(G[poped][i]== 1 and (i not in Visit)):
                queue.append(i)
                Visit.append(i)

    return Visit



def DFS(s,Visited):
    Visited.append(s)
    # s 노드에서 갈 수 있는 연결노드로 들어가기
    for i in range(1, N + 1):
    	# 해당 노드는 연결이 있으면서, 방문한적이 없어야 함.
        if (G[s][i] == 1 and (i not in Visited)):
            DFS(i,Visited)
    return Visited



visit = []

# 이건 리스트로 나와서 아래처럼 처리.
# print(DFS(V,visit))
# print()
# print(BFS(G,V))

for i in DFS(V,visit):
    print(i,end=" ")
print()

for i in BFS(G,V):
    print(i,end=" ")

 

---

문제는 아래 ↓링크↓

 

 

1260번: DFS와 BFS