Backjoon_1260 DFS와BFS_Python풀이

[문제]

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

[입력]

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

[출력]

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

[TestCase]

[INPUT]

*** TEST1 ***
4 5 1
1 2
1 3
1 4
2 4
3 4
*** TEST2 ***
5 5 3
5 4
5 2
1 2
3 4
3 1
*** TEST3 ***
1000 1 1000
999 1000

[OUTPUT]

*** TEST1 ***
1 2 4 3
1 2 3 4
*** TEST2 ***
3 1 2 5 4
3 1 4 2 5
*** TEST3 ***
1000 999
1000 999

[알고리즘 분류]

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

[문제 요약]

• 입력 받은 값을 DFS, BFS로 탐색한 과정을 출력하여라.

[사용 알고리즘]

DFS(Depth First Serch)

• 사전에 스택 또는 재귀 알고리즘 학습 필요
• 깊이 우선 탐색 이므로, 가장 좌측 수칙으로 우선 탐색
• 조건에 해당하지 않은 노드를 발견 시 가장 가까운 갈림길로 돌아와 우측으로 - 한 칸씩 이동하며 다시 탐색
• BFS(너비 우선 탐색)에 비해 간단하지만 느림
• 주로 모든 노드를 탐색할 때 사용

BFS(Breadth First Serch)

• 사전에 큐 또는 재귀 알고리즘 학습 필요
• 너비 우선 탐색 이므로, 수직이 아닌 수평을 기준으로 이동
• 즉, 가장 가까운 노드를 먼저 탐색
• 주로 특정 장소에서 다른 장소로 이동이 가능한지 알아볼 때 사용

from collections import deque

# 변수
NodeCnt, LinkCnt, StrNum = map(int, input().split())
dList = [0] * (NodeCnt + 1)
bList = [0] * (NodeCnt + 1)
TotalList = [[0]*(NodeCnt + 1) for i in range(NodeCnt + 1)] # 연결된 노드인지 2차원 배열을 이용하여 확인


def DFS(Node) : # DFS 함수
    dList[Node] = 1 # 해당 위치 1로 변경
    print(Node, end =  ' ')
    for i in range(1, NodeCnt + 1) : # 리스트의 벨류 인덱스 값 까지 반복 
        if dList[i] == 0 and TotalList[Node][i] == 1 : # 해당 노드 첫 방문 및 연결된 노드인지 확인
            DFS(i) # 재귀
            

def BFS(Node) : # BFS 함수
    queue = deque([Node]) # queue에 현재 노드 값 deque
    bList[Node] = 1 # 현재 위치 1로 변경
    while queue : # queue 모두 순회
        Node = queue.popleft() # queue의 좌측 부터 차례로 pop
        print(Node, end = ' ')
        for i in range(1, NodeCnt + 1) :
            if bList[i] == 0 and TotalList[i][Node] == 1 : # 해당 노드 첫 방문 및 연결된 노드인지 확인
                queue.append(i) # queue 맨 뒤에 현재 값 저장
                bList[i] = 1 # 현재 위치 1로 변경


for i in range(LinkCnt) : # LinkCnt만큼 반복
    fnt, bak = map(int, input().split()) # 입력 값을 공백 기준으로 나누고 해당 값을 int형으로 fnt, bak에 저장
    TotalList[fnt][bak] = TotalList[bak][fnt] = 1

DFS(StrNum)
print()
BFS(StrNum)

[풀이 요약]

1. NodeCnt, LinkCnt, StrNum 변수를 입력한다.
2. dList, bList, TotalList 변수들을 초기화한다.
3. TotalList는 연결된 노드인지를 확인하기 위한 2차원 배열이다.
4. 연결 정보를 입력받고, TotalList에 연결 정보를 저장한다.
5. DFS(StrNum)을 호출하여 DFS를 시작한다.
6. DFS 함수는 시작 노드 StrNum을 기준으로 연결된 노드들을 재귀적으로 탐색하며 방문한 노드들을 출력 후 줄바꿈 한다.
7. BFS(StrNum)을 호출하여 BFS를 시작한다.
8. BFS 함수는 시작 노드 StrNum을 기준으로 연결된 노드들을 큐를 이용하여 탐색하며 방문한 노드들을 출력한다.