[백준 1260번 파이썬] DFS 와 BFS

백준 1260번 링크)

---

---

인접행렬 : 그래프에서 어떤 노드들끼리 연결되었는지를 나타내는 이차원 행렬

adj = [[0, 1, 1, 1],
       [1, 0, 0, 1],
       [1, 0, 0, 1],
       [1, 1, 1, 0]]

adj = [[0, 0, 0, 0, 0],
       [0, 0, 1, 1, 1],
       [0, 1, 0, 0, 1],
       [0, 1, 0, 0, 1],
       [0, 1, 1, 1, 0]]
# 노드와 인덱스의 번호를 같게하기 위해서 matrix=[[0]*(n+1) for _ in range(n+1)] 에서 n+1만큼 하는 것이다

import sys
input=sys.stdin.readline
n,m,v=map(int,input().split())

matrix=[[0]*(n+1) for _ in range(n+1)] # 간편히 미리 0으로 채운 (n+1)x(n+1) 행렬을 만들어둔다

for _ in range(m):
    adj=list(map(int,input().split()))
    matrix[adj[0]][adj[1]]=1
    matrix[adj[1]][adj[0]]=1 # 인접행열에 연결된 곳들은 1로 채우기

def dfs(start,row, visited):
    visited+=[start]
    for search in range(len(row[start])):
        if row[start][search] and search not in visited:
            visited=dfs(search,row,visited) #재귀적
    return visited

def bfs(start,row,visited):
    queue=[start]
    visited=[start]
    while queue:
        point=queue.pop(0) # 큐의 맨 앞의 것을 빼줌 ( deque의 popleft()와 같다)
        for search in range(len(row[start])):
            if row[start][search] and search not in visited:
                visited+=[search]
                queue+=[search]
    return visited

print(*dfs(v,matrix,[])) # * : 리스트를 풀어줌
print(*bfs(v,matrix,[]))