4일차 - 그래프 경로

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] = 1
    
    def dfs(self, start):
        self.visited[start] = 1
        
        for i in range(self.size):
            if self.matrix[start][i] == 1 and self.visited[i] == 0:
                self.dfs(i)
    
    def dfs2(self, start):
        stack = [start]

        while stack:
            var = stack.pop()
            
            if self.visited[var] == 0:
                self.visited[var] = 1
                
                for w in range(self.size):
                    if self.matrix[var][w] == 1:
                        stack.append(w)
    
    def return_visited(self):
        return self.visited

t = int(input())
ans = list()

for _ in range(t):
    v, e = map(int, input().split())
    g = Graph(v)

    for _ in range(e):
        v1, v2 = map(int, input().split())
        g.addEdge(v1-1, v2-1)

    s, goal = map(int, input().split())
    g.dfs2(s-1)

    visit_record = g.return_visited()

    if visit_record[goal-1] == 1:
        ans.append(1)
    else:
        ans.append(0)
    

for i in range(t):
    print(f"#{i+1} {ans[i]}")

 

DFS도 이진탐색처럼 지인짜 오랜만에 구현해본 것 같다...

예전에 썼던 코드 보면서 클래스 만들고 써봤는데 확실히 가독성은 좋은 것 같다..

 

dfs 는 재귀로 구현한 것이고 dfs2 는 스택과 반복문을 이용해서 구현해보았다~!