백준 1260번 DFS와 BFS 파이썬(Python)

안녕하세요, 츄르 사려고 코딩하는 집사!      코집사입니다.

 

1. 코드입니다.

N, M, V = map(int, input().split())
matrix = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    link = list(map(int, input().split()))
    matrix[link[0]][link[1]] = 1
    matrix[link[1]][link[0]] = 1


def dfs(current_node, row, foot_prints):
    foot_prints += [current_node]
    for search_node in range(len(row[current_node])):
        if row[current_node][search_node] and search_node not in foot_prints:
            foot_prints = dfs(search_node, row, foot_prints)
    return foot_prints


def bfs(start):
    queue = [start]
    foot_prints = [start]
    while queue:
        current_node = queue.pop(0)
        for search_node in range(len(matrix[current_node])):
            if matrix[current_node][search_node] and search_node not in foot_prints:
                foot_prints += [search_node]
                queue += [search_node]
    return foot_prints


print(*dfs(V, matrix, []))
print(*bfs(V))

 

이 코드는 아래의 디스프로그래머님의 블로그의 코드입니다.

제가 짠 코드는 너무 복잡스러워서 깔끔하게 짠 코드를 올리는게 맞다고 생각합니다.

https://this-programmer.com/entry/%EB%B0%B1%EC%A4%801260%ED%8C%8C%EC%9D%B4%EC%8D%AC-DFS%EC%99%80-BFS

[백준/1260/파이썬3(python3)] DFS와 BFS

 

2. 해설입니다.

N, M, V = map(int, input().split()) #N, M, V에 각 입력값 입력

matrix = [[0] * (N + 1) for _ in range(N + 1)] #Matrix라는 빈 2차원 배열에 0을 입력 N값에 따라 크기 입력

 
for _ in range(M): 
    link = list(map(int, input().split())) 
    matrix[link[0]][link[1]] = 1 
    matrix[link[1]][link[0]] = 1 
# M의 크기만큼 range 함수를 통해 link라는 리스트에 입력을 합니다. 즉, 간선의 입력을 받습니다.
# 그 후, matrix의 2차원 배열에 link 리스트의 첫번째 값과 두번째 값의 위치에 1을 입력합니다.[간선이 있는 곳에 1 입력]

def dfs(current_node, row, foot_prints): 
    foot_prints += [current_node] 
    for search_node in range(len(row[current_node])): 
        if row[current_node][search_node] and search_node not in foot_prints: 
            foot_prints = dfs(search_node, row, foot_prints) 
    return foot_prints 
# foot_prints는 발자취를 입력해주는 변수로 결과값을 출력해주는 변수

def bfs(start): 
    queue = [start] 
    foot_prints = [start] 
    while queue: 
        current_node = queue.pop(0) 
        for search_node in range(len(matrix[current_node])): 
            if matrix[current_node][search_node] and search_node not in foot_prints: 
                foot_prints += [search_node] 
                queue += [search_node] 
    return foot_prints 


print(*dfs(V, matrix, [])) 
print(*bfs(V))