[백준/Python] 1260 : DFS와 BFS

 

 

 

자료구조 수업때 배운 dfs와 bfs 알고리즘으로 쉽게 풀 수 있었던 문제!

 

class Node:
    def __init__(self, value):
        self.data = value

class Graph:
    def __init__(self):
        self.graph = {}
        self.visit = []
        self.queue = []
    
    def create(self, v, data): # 인접리스트 graph[v]에 data추가
        node = Node(data)
        if v not in self.graph:
            self.graph[v] = []
        self.graph[v].append(node)

    def addq(self, v): self.queue.append(v)

    def deleteq(self):
        if self.queue:
            return self.queue.pop(0)
        else:
            print("Queue Empty")

    def dfs(self, v):
        self.visit.append(v)
        for node in sorted(self.graph.get(v, []), key=lambda x: x.data): # graph[v]는 정점 v 의 인접 리스트
            if node.data not in self.visit:
                self.dfs(node.data)
    
    def bfs(self, v):
        self.visit.append(v)
        self.addq(v)
        while self.queue:
            v = self.deleteq()
            for node in sorted(self.graph.get(v, []), key=lambda x: x.data):
                if node.data not in self.visit:
                    self.visit.append(node.data)
                    self.addq(node.data)

g = Graph()

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

import sys
input = sys.stdin.read
nodes = input().splitlines()
for node in nodes:
    a, b = map(int, node.split())
    g.create(a, b)
    g.create(b, a)


g.dfs(V) # 깊이 우선 탐색
print(' '.join(map(str, g.visit)))
g.visit = []
g.bfs(V)  # 너비 우선 탐색
print(' '.join(map(str, g.visit)))

 

 

첫째줄에 N, M, V를 일렬로 입력 받는데, 이후 N과 M을 사용해서 for문을 사용할 수도 있겠지만 입력이 많아질 것을 고려해서 sys.stdin.read로 한 번에 입력받고 nodes 변수에 넣어줄때만 splitlines()를 사용하여 저장하였다.

따라서 사실상 이용하는 변수는 dfs와 bfs 호출할 때 사용하는 V밖에 없는 셈!

 

첫째 줄을 입력 받은 후 앞서 말했듯이 nodes 리스트가 만들어졌다면, nodes의 원소인 node(순서쌍)을 차례로 뽑아서 노드화시켜야 하므로 for문을 통해 하나씩 추출하여 create한다.

이 문제에서는 양방향으로 제시하고 있으므로, create(a, b)와 create(b, a)를 모두 진행해줘야 한다.

 

다음으로 Graph 클래스와 내부 메소드를 설명해보자면 다음과 같다.

 

create(v, data) => self.graph[v]에 data 추가

addq(v) => v를 큐에 삽입

deleteq() => 큐의 최하단부 원소 제거 및 반환

 

dfs(v) => 깊이 우선 탐색 함수로서, 인자로 받은 v 노드를 visit에 기록(append)한 뒤 해당 노드에 연결되어 있는 다른 정점들 중에서 가장 정점 번호가 작은 것을 먼저 방문하여 재귀적으로 연결을 이어나간다.

 

bfs(v) => 너비 우선 탐색 함수로서, 인자로 받은 v 노드를 방문 기록인 visit 리스트와 큐에 각각 추가한다. 

while문에서 큐의 최하단부 원소롤 pop된 v 노드를 기준으로 해당 노드에 연결되어 있는 다른 정점들 중 가장 정점 번호가 작은 것을 방문하여 visit 리스트와 큐에 각각 저장하는 작업을 큐가 비어있을 때까지 반복한다.

 

bfs와 dfs에서 모두 sorted(self.graph.get(v, []), key=lambda x: x.data)  를 사용하였는데, 이는 인접 리스트인 graph를 정렬하여 방문할 수 있는 정점 중 정점 번호가 작은 것을 먼저 방문하도록 한 것이다.

 

현재 visit은 리스트 형태이므로, 예제 출력 결과처럼 나오도록 하기 위해 마지막에 ' '.join(map(str, g.visit)) 처리를 해준다.