[알고리즘] 백준 - 1260 (DFS와 BFS) / 파이썬

import sys

n, m, v = map(int, sys.stdin.readline().strip().split()) #3개 입력

edge = [[] for _ in range(n + 1)] #노드 갯수만큼 반복해서 만듬

for i in range(m):
    a, b = map(int, sys.stdin.readline().strip().split())
    edge[a].append(b)
    edge[b].append(a)

for e in edge:
    e.sort(reverse=True)


def DFS():
    dfs = []
    stack = [v]
    visit = [0] * (n+1)
    while stack:
        node = stack.pop()
        if visit[node]:
            pass
        else:
            visit[node] = 1
            dfs.append(node)
            stack += edge[node]
    return dfs


def BFS():
    bfs = []
    que = [v]
    visit = [0] * (n+1)
    visit[v] = 1
    while que:
        node = que.pop()
        bfs.append(node)
        for i in reversed(edge[node]):
            if visit[i]:
                continue
            visit[i] = 1
            que = [i] + que 
    return bfs


print(*DFS())
print(*BFS())

파이썬으로 갈아타기

DFS

1. 입력 받기  map(int, sys.stdin.readline().split())
2. 인접 리스트 edge = [[] for _ in range(n + 1)] 혹은
인접 행렬 graph[[0] *(n+1) for  _ in range(n+1)] 만들기
3. 정점 번호가 적은것부터 탐색하기 때문에 e.sort(reversr=True)
4. 반환용 dfs 리스트와  스택 , 정점을 방문한 여부를 파악하는 visit 리스트 생성
5. 스택에 넣으면서 하나씩 뺌 
6. 스택에서 뺀 원소를 방문하지 않으면 방문처리하고 그 원소와 연결된 인접 리스트들을 전부 스택에 넣음 
7. 6을 반복하고 반환


BFS 

3. 까지 동일
4. 반환용 bfs리스트와 큐(여기서는 배열로 진행) , 방문 여부 체크를 위한 visit 생성
5. 큐를 돌면서 하나씩 pop  (왼쪽에서 들어와서 오른쪽으로 나간다고 가정)
6. 낮은값 부터 탐색하기 위해서 reversed를 사용하여 탐색
7. 6을 반복하고 반환