59. Python 백준 1260 번 DFS와 BFS stack, queue를 이용한 풀이. Stack이란? Queue란? Deque 이란? 파이썬 stack, Deque

 

안녕하세요. 코딩하는 덕구입니다. Python 백준 1260 번 DFS와 BFS 입니다.

그래프 탐색 문제입니다. stack, queue, deque 에 관한 설명은 아래에 있습니다.

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

1260번: DFS와 BFS

 

DFS는 stack을 이용해서 쉽게 풀어낼 수 있는데요!

stack은 데이터를 저장하는 방식 중 하나입니다. 다시말해 일종의 자료구조 입니다.

stack은 물건을 담을 수 있는 상자라고 생각하시면 됩니다.

예를들어 1, 2... n 이라는 숫자들을 순서대로 stack에 저장한다고 했을 때 다음과 같은 모양이 되고,

자료에 관한 접근은 맨 위에서만 가능해 집니다. 

예를들어  pop이란 연산을 통해. 해당 데이터 값을 리턴하고, 맨 위 값을 삭제합니다.

맨 위의 값이 삭제 됐으므로,  그 다음 값인 n-1이 맨 위의 값이 되겠죠

이런식으로 연산을 하게 되면 자연스럽게 가장 먼저 들어온 자료는, 가장 마지막에 접근이 가능하고

반대로 가장 마지막에 들어온 자료는, 가장 먼저 접근이 가능해지죠.

이를 LIFO 혹은 FILO, 

Last In First Out, First in Last Out 이라고 합니다.

 

어떻게 하면 stack으로 DFS를 구현할 수 있을까요?

1. 처음 방문 노드를 stack에 넣는다.

2. stack이 비어있는지 확인하고, 비어있지 않다면 노드를 pop 한다.

3. pop 된 노드가 한번도 방문하지 않은 노드라면 방문한다.

4. 방문한 노드에서 다른 노드로 방문할 수 있는 모든 노드를 stack에 넣는다.

5. 2~4를 반복한다.

 

위의 규칙대로 진행을 하면 가장 위에 있는 노드를 방문하면서

나중에 방문할 곳들은 그 밑의 stack에 쌓여있게 되기 때문에

DFS 방식으로 탐색이 가능합니다. 코드로 구현해봅시다.

 

 먼저 그래프의 뼈대를 그려주고

graph = [[0 for _ in range(N+1)]for _ in range(N+1)]

 

어떤 노드에서 다른 노드로 가는 간선이 존재한다면 해당 간선을 1로 표시합니다.

간선이 없다면 0 이겠죠

for _ in range (M):
    i, j = map(int, input().split())
    graph[i][j] = 1
    graph[j][i] = 1

 

한 노드를 방문 했는지 안했는지 저장하기 위한 배열도 하나 만들어 줍니다. 

visited = [False for _ in range (N+1)]

사전준비는 끝났습니다.

 

dfs 방식으로 그래프를 탐색하는 함수 dfs를 만들어보았습니다.

def dfs(V):
    stack = [V]
    order = ''
    while stack:
        i = stack.pop()
        if visited[i] == False:
            visited[i] = True
            order += str(i) + ' '
            for j in range (N, 0, -1):
                if graph[i][j] == 1:
                    stack.append(j)
    return order[:-1]

 

함수 안에서는 DFS 에 활용할 stack을 정의해주고, 처음에 시작할 노드를 넣어줍니다.

이후 노드i 를 stack에서 pop 하여 visited[i] 를 체크하여 방문했는지 확인한 후

방문하지 않았으면 방문합니다. visited[i] = True로 표시

방문한 노드를 순서대로 출력할 양식 order에 해당 노드를 추가해주고

노드 i 에서 그래프에 간선을 체크하며, 다른 노드로의 간선있다면 stack에 쌓아줍니다.

이때, 백준에서는 여러 간선이 있을 때 작은 수 부터 방문하라는 조건이 있었으므로

큰 수부터 체크해서 stack에 넣습니다. (가장 마지막에 들어오는 숫자부터 방문하게 되므로 LIFO)

마지막에는 order를 리턴해주면 됩니다.

 

print(dfs(V))

출력은 이렇게 하면 되겠죠

 

 

다음은 BFS 입니다.

queue를 이용하여 구현할 수 있습니다.

queue는 stack 과 마찬가지로 일종의 자료구조 인데요

 

마치 놀이기구 대기열 처럼

가장 먼저 들어온 숫자는 가장 먼저 나가게 되는

FIFO. First In Fisrt Out 구조를 가지게 됩니다.

아까 stack을 구현해서 DFS를 구현 했었는데요

stack 대신 queue를 넣는다면 어떻게 될까요??

 

stack은 가장 최근에 들어온 노드가 가장 먼저 나가기 때문에 DFS가 됐지만

queue는 먼저 들어온 노드 순서대로 노드가 출력이 되기 때문에 첫 노드에서 방문할 수 있는 노드들이

queue에 쌓이게 되고, 해당 노드들을 방문하면서 또 방문할 수 있는 노드들이 쌓이면서

너비우선 탐색이 됩니다.

 

BFS 구현입니다.

1. 처음 방문 노드를 queue에 넣는다.

2. queue가 비어있는지 확인하고, 비어있지 않다면 노드를 pop 한다.

3. pop 된 노드가 한번도 방문하지 않은 노드라면 방문한다.

4. 방문한 노드에서 다른 노드로 방문할 수 있는 모든 노드를 queue에 넣는다.

5. 2~4를 반복한다.

def bfs(V):
    q = deque()
    q.append(V)
    order = ''
    while q:
        i = q.popleft()
        if visited[i] == False:
            visited[i] = True
            order += str(i) + ' '
            for j in range(1, N+1):
                if graph[i][j] == 1:
                    q.append(j)
    return order[:-1]

 

마찬가지로 출력은  아래와 같이 하면 되겠죠

print(bfs(V))

 

 

다음은 deque 입니다. 위의 코드에서 수상한 점을 눈치 채신 분들도 계실텐데요

queue를 이용한다면서

q = deque()

deque을 사용했죠

deque이란 무었일까요?

 

stack 과 queue가 합쳐진 자료구조입니다. 앞 뒤 모두 넣을 수 있고,

앞 뒤 모두 출력 가능합니다.

다만 자료의 중간에는 접근이 불가하죠 이것이 array와 다른 점입니다.

 

deque에서 뒤에만 입력하고, 앞에서만 출력하면 queue 와 같이 동작할 수 있겠죠

반대로 queue를 뒤에서만 입력하고, 뒤에서만 출력하면 stack처럼 사용할 수 있게 됩니다.

 

 

Python 백준 1260 번 DFS와 BFS 최종 코드입니다.

from collections import deque
N, M, V = map(int, input().split())
graph = [[0 for _ in range(N+1)]for _ in range(N+1)]

for _ in range (M):
    i, j = map(int, input().split())
    graph[i][j] = 1
    graph[j][i] = 1

visited = [False for _ in range (N+1)]

def dfs(V):
    stack = [V]
    order = ''
    while stack:
        i = stack.pop()
        if visited[i] == False:
            visited[i] = True
            order += str(i) + ' '
            for j in range (N, 0, -1):
                if graph[i][j] == 1:
                    stack.append(j)
    return order[:-1]

def bfs(V):
    q = deque()
    q.append(V)
    order = ''
    while q:
        i = q.popleft()
        if visited[i] == False:
            visited[i] = True
            order += str(i) + ' '
            for j in range(1, N+1):
                if graph[i][j] == 1:
                    q.append(j)
    return order[:-1]

print(dfs(V))
visited = [False for _ in range (N+1)]
print(bfs(V))

Python 백준 1260 번 DFS와 BFS 와 함께 Stack, Queue, Deque 에 대한 설명 이었습니다.

 

감사합니다.