[백준 1260] DFS와 BFS 문제풀이

문제 링크: https://www.acmicpc.net/problem/1260

문제

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

입력

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

출력

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

예제

입력

출력

1 2 4 3
1 2 3 4

풀이 노트

import sys
from collections import deque

input = sys.stdin.readline

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

graph = [[] for _ in range(N + 1)]
visited_dfs = [False] * (N + 1)
visited_bfs = [False] * (N + 1)

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for i in range(N + 1):
    graph[i].sort()


def dfs(num):
    print(num, end=" ")
    visited_dfs[num] = True
    for val in graph[num]:
        if not visited_dfs[val]:
            dfs(val)


def bfs(num):
    queue = deque()
    queue.append(num)
    visited_bfs[num] = True
    while queue:
        q = queue.popleft()
        print(q, end=" ")
        for val in graph[q]:
            if not visited_bfs[val]:
                visited_bfs[val] = True
                queue.append(val)


dfs(V)
print()
bfs(V)
print()

1. 정점 관리 중첩 리스트와 방문 체크 리스트 생성하기

graph = [[] for _ in range(N + 1)]
visited_dfs = [False] * (N + 1)
visited_bfs = [False] * (N + 1)

입력으로 주어지는 N 개의 정점간의 연결을 관리하기 위한 graph 중첩 리스트를 만드는데 이때 크기를 N+1로 하는 이유는 정점은 최소값이 1이고 인덱스는 0에서 시작하기 때문에 정점을 관리하는 중첩 리스트인 graph를 사용하기 쉽게 N에 1을 더한 크기로 생성하는것입니다.
visited_dfs, visited_bfs 두 리스트는 dfs, bfs 두 알고리즘으로 정점을 이동할때 이미 방문한 정점을 중복 방문하지 않기 위해 만든 리스트 입니다. graph 리스트와 마찬가지로 N+1 크기로 지정했으며 처음엔 아무곳도 방문하지 않았으므로 False 가 기본값 입니다.

2. 간선 정보 입력, graph 정렬

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for i in range(N + 1):
    graph[i].sort()

간선정보는 이어져있는 두 정점의 정보를 받습니다. 양쪽에서의 연결을 모두 확인하기 위해 graph 에 각 정점을 기준으로 상대 정점을 요소로 append 하여 넣어 줍니다.
위의 예시로 만들어진 graph 리스트의 형태는 다음과 같습니다.

<1>
graph[1] = [2]
graph[2] = [1]

<2>
graph[1] = [2,3]
graph[2] = [1]
graph[3] = [1]

<3>
graph[1] = [2,3,4]
graph[2] = [1]
graph[3] = [1]
graph[4] = [1]

<4>
graph[1] = [2,3,4]
graph[2] = [1,4]
graph[3] = [1]
graph[4] = [1,2]

<5>
graph[1] = [2,3,4]
graph[2] = [1,4]
graph[3] = [1,4]
graph[4] = [1,2,3]

문제의 조건으로 정점과 연결된 정점이 여러개일 경우 가장 작은값부터 이동한다고 되있으므로 sort() 메서드로 정렬 과정을 진행합니다.
정렬까지 진행된 graph 리스트의 최종 형태는 다음과 같습니다.

graph[1] = [2,3,4]
graph[2] = [1,4]
graph[3] = [1,4]
graph[4] = [1,2,3]

3. DFS 깊이 우선 탐색 알고리즘

def dfs(num):
    print(num, end=" ")
    visited_dfs[num] = True
    for val in graph[num]:
        if not visited_dfs[val]:
            dfs(val)

DFS는 깊이 우선 탐색 알고리즘으로 연결된 정점의 가장 하위항목까지 먼저 이동후 더이상 연결 지점이 없으면 다시 이전 단계로 돌아와서 연결된 정점이 있다면 같은 동작을 반복수행하는 탐색 알고리즘 입니다.

3.1 방문한 정점 위치 출력, 방문 체크

print(num, end=" ")
visited_dfs[num] = True

문제에서 가장 처음에 시작할 정점의 위치를 num 으로 받고 print 메서드로 방문한 정점에 대해 출력합니다.
visited_dfs 리스트에서 정점의 위치를 True값으로 변경하여 아래에 있는 if 조건에서 통과되지 않도록 합니다.

3.2 정점과 연결된 정점 찾고 재귀 호출하기

for val in graph[num]:
    if not visited_dfs[val]:
        dfs(val)

graph 리스트에 대해 반복을 진행하는데 sort 과정을 거쳤기 때문에 문제에서 요구하는 연결된 정점중 가장 작은 정점부터 이동해야하는 조건은 자동으로 만족 됩니다.
val은 num 정점과 연결된 정점이고 if 조건에 따라 val 정점을 방문하지 않았다면 if 조건을 만족하고 dfs 함수를 재귀 호출하게 됩니다.
재귀 호출하게 되면 3.1 단계를 다시 수행하면서 방문한 정점 정보를 출력하고 방문 체크 리스트를 업데이트 합니다.
graph, visited_dfs 두개의 리스트의 움직임은 다음과 같습니다.

001 => visited_dfs[1] = True
       graph[1] val = 2 <통과>
002 => visited_dfs[2] = True
       graph[2] val = 1 <실패>
       graph[2] val = 4 <통과>
003 => visited_dfs[4] = True
       graph[4] val = 1 <실패>
       graph[4] val = 2 <실패>
       graph[4] val = 3 <통과>
004 => visited_dfs[3] = True
       graph[3] val = 1 <실패>
       graph[3] val = 4 <실패>
종료

dfs의 결과는 순서대로 1 2 4 3 이 됩니다.

4. BFS 너비 우선 탐색 알고리즘

def bfs(num):
    queue = deque()
    queue.append(num)
    visited_bfs[num] = True
    while queue:
        q = queue.popleft()
        print(q, end=" ")
        for val in graph[q]:
            if not visited_bfs[val]:
                visited_bfs[val] = True
                queue.append(val)

BFS 너비 우선 탐색 알고리즘은 연결된 정점을 모두 방문후에 다음 단계로 넘어가서 반복하는 알고리즘입니다.
BFS 알고리즘은 일반적으로 큐를 활용하여 해결합니다. 반대로 DFS는 보통 재귀함수를 사용합니다.

4.1 큐에 첫번째 정점 추가, 방문 체크

queue = deque()
queue.append(num)
visited_bfs[num] = True

메서드 진입할때 queue 를 생성하고 첫 시작 정점을 큐에 입력합니다.
방문 체크 리스트 visited_bfs 도 업데이트를 합니다.

4.2 루프에서 현재 정점 큐에서 출력, 인접 정점 확인

while queue:
    q = queue.popleft()
    print(q, end=" ")
    for val in graph[q]:
        if not visited_bfs[val]:
            visited_bfs[val] = True
            queue.append(val)

queue.popleft() 기능으로 현재 큐에있는 정점정보를 출력하는데 이때의 정점은 현재 방문중인 정점 입니다.
whlie 루프의 조건은 queue가 유효할때이고 모든 정점을 방문했다면 queue에 append 하지 않으므로 종료됩니다.
for 루프는 현재 정점 q 기준으로 연결된 정점 val 에 대해 모두 방문 체크를 하면서 만약 방문 하지 않은 정점은 방문 체크를 True로 업데이트 하고 큐에 정점을 입력합니다.
graph, visited_bfs 두개의 리스트의 움직임은 다음과 같습니다.

001 =>  visited_bfs[1] = True
        q = 1 queue = []
002 =>  graph[1] val = 2 / visited_bfs[2] = True / queue = [2]
        graph[1] val = 3 / visited_bfs[3] = True / queue = [2,3]
        graph[1] val = 4 / visited_bfs[4] = True / queue = [2,3,4]
003 =>  q = 2 queue = [3,4]
004 =>  graph[2] val = 1 visited_bfs[1] <이미 방문>
        graph[2] val = 4 visited_bfs[4] <이미 방문>
005 =>  q = 3 queue = [4]
006 =>  graph[3] val = 1 visited_bfs[1] <이미 방문>
        graph[3] val = 4 visited_bfs[4] <이미 방문>
007 =>  q = 4 queue = []
        graph[4] val = 1 visited_bfs[1] <이미 방문>
        graph[4] val = 2 visited_bfs[2] <이미 방문>
        graph[4] val = 3 visited_bfs[3] <이미 방문>
queue 빈값으로 루프 종료

bfs의 결과는 순서대로 1 2 3 4 가 됩니다.

저작자표시 변경금지

KSR의 저장소