(Python) boj_1260

 

<문제>

 

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

1260번: DFS와 BFS

 

<풀이 과정>

 

from collections import deque

def bfs(graph,v,visited1):

    queue = deque([v])
    visited1[v] = True

    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited1[i]:
                queue.append(i)
                visited1[i] = True

def dfs(graph,v,visited):
    visited[v] = True
    print(v, end = ' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

n,m,v = map(int,input().split())

graph = [[] for i in range(n+1)]
'''
graph = []

for _ in range(n+1):
    graph.append([])
'''

for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(1,n+1):
    graph[i].sort()


visited = [False]*(n+1)
visited1 = [False]*(n+1)
dfs(graph,v,visited)
print()
bfs(graph,v,visited1)

 

 

dfs와 bfs에 해당하는 값을 한 번에 구하는 문제이기에 함수를 2개 만들어 주었습니다.

 

-- 먼저 DFS입니다. --

 

문제의 조건에서 '다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다'라고 하였는데요. 저는 처음에 두 정점의 번호를 아무 생각 없이  graph 리스트에 넣어줬었습니다. (graph = [ [], [1,2], [1,3] ----]과 같이요)

 

하지만 해당 graph 이차원 리스트의 용도(쓰임?)은 n번 노드와 연결된 것의 모음을 나타내기 위함입니다. 

 

즉, graph = [ [] , [1,2,3], [4,5] ]와 같이 이차원 리스트가 있다면, 비어있는 []는 배열의 번호를 조금 더 쉽게 생각해 주기 위한 장치이고, graph [1]의 [ 1 , 2 , 3 ]은 1번 노드와 연결된 것(노드)의 모음이고, 마찬가지로 [ 4 ,5 ]는 2번 노드와 연결된 노드의 모음입니다.

 

위와 같이 graph 리스트를 제대로 생성해주었음에도 불구하고, dfs가 잘 구해지지 않았었는데, 그 이유는 graph의 각 리스트 요소값들이 정렬되어 있지 않아서였습니다. (번호가 낮은 거 높은 거 뒤죽박죽...)

흔히 DFS,BFS 에서 번호가 낮은 인접노드부터 방문하는 것을 가정하고 문제를 풀기에, 저도 sort()를 이용하여 번호가 낮은 것을 먼저 방문할 수 있도록 해주었습니다. (하지만 문제의 요구에 따라 방문기준이 달라질 수 있다고 합니다.)

 

visited = [False] *n 은 방문처리를 위한 리스트입니다. 

 

DFS는 방문하지 않은 노드를 계속해서 방문한다는 점에서 깊이 우선으로 최대한 깊게 그래프를 탐색할 수 있습니다. 

 

--BFS--

 

BFS 알고리즘은 큐 자료 구조를 이용하기에, from collections import deque 과 같이 deque 라이브러리를 사용해 줍니다. 

 

예제 1 입력 값을 기준으로 풀이를 진행해 보겠습니다. 

 

우선 각 노드들의 연결 상태는 다음과 같습니다. graph = [ [ ] , [ 2 , 3 , 4 ] ,  [ 1 , 4 ] , [ 1 , 4 ] ,  [ 1 , 2 , 3] ] 

 

queue = deque( [ v값(1) ] ) 

 

visited1 [ 1 ] = True

 

while queue: # 큐가 빌 때까지 반복합니다. ( 현재 queue는 deque([1])인 상태입니다. ) 

 

queue.popleft()를 통해 v 값이 1임을 알 수 있습니다. 

 

print( 1, end = ' ')

 

for i in graph[ 1 ]:  graph[1] 이 [2,3,4] 이므로 

for i in [ 2 , 3 , 4 ]와 같이 표현될 수 있습니다. 

 

if not visited[2]: False 상태이고, not이니 True로 if문이 동작하게 됩니다. 

queue.append(2)

visited[2] = True 가 됩니다.  그럼 현재 queue에는 2인 요소값이 존재하게 됩니다. 

 

그리고 for문에 의해 i = 3, i = 4인 경우도 동작 되게 됩니다. 그렇다면 queue에는 2,3,4의 요소들이 들어 있게 됩니다.

 

다시 while queue:입니다. queue가 비어있지 않으므로 다시 while문이 동작되게 됩니다. 

 

v = 2가 되며 for i in graph [2]:로 2번째 노드를 기준으로 아직 방문하지 않은 인접한 노드들을 큐에 삽입해 줍니다.

 

하지만, if not visited1 [ 1 ]은 True에서 not이 되므로 False가 되어 if문이 동작하지 않습니다. visited1 [4]의 경우도

마찬가지입니다. 

 

다시 순서가  while로 돌아가게 되고, v = 3이 되며 위의 과정들을 반복합니다.. v = 4일 때도 위의 과정이 반복됩니다.

 

그래서 결괏값은 1 2 3 4가 출력이 되게 됩니다. 

 

 

BFS는 너비 우선 탐색이며  그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다. 

( 출발 노드에서 거리가 가까운 노드부터 우선적으로 방문하며, 거리가 가장 먼 노드가 가장 마지막에 탐색이 됩니다. )