1260 - DFS와 BFS

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

1260번: DFS와 BFS

 

- DFS

- BFS

 

import sys
input = sys.stdin.readline

from collections import deque

class Graph:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0] * size for _ in range(size)]
        self.visited = [0] * size

    def addEdge(self, v1, v2):
        self.matrix[v1][v2] = self.matrix[v2][v1] = 1

    def dfs(self, start):
        self.visited[start] = 1
        print(start+1, end=" ")
        for i in range(self.size):
            if self.matrix[start][i] == 1 and self.visited[i] == 0:
                self.dfs(i)

    def bfs(self, start):
        q = deque([start])
        self.visited[start] = 1

        while q:
            k = q.pop()
            print(k+1, end=" ")
            for i in range(self.size):
                if self.matrix[k][i] == 1 and self.visited[i] == 0:
                    q.appendleft(i)
                    self.visited[i] = 1
    
    def resetVisited(self):
        self.visited = [0] * self.size

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

g = Graph(n)
for _ in range(m):
    n1, n2 = map(int, input().split())
    g.addEdge(n1-1, n2-1)

g.dfs(v-1)
print()
g.resetVisited()
g.bfs(v-1)

기본 그래프 탐색 구현 문제이다

 

(삘받아서 그래프 문제 하나 더 함ㅎㅎ)

 

 

dfs는 스택보다 재귀로 구현하는 것이 훨씬 간단하다는 것을 알앗다