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
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))
'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
[백준 알고리즘] 백준 11399번 ATM 파이썬(Python) (0) | 2020.01.03 |
---|---|
백준 18108번 파이썬(Python) 1998년생인 내가 태국에서는 2541년생?! (0) | 2019.12.20 |
백준 15953번 상금 헌터 파이썬(Python) (0) | 2019.11.30 |
백준 2606번 바이러스 파이썬(Python) (0) | 2019.11.30 |
백준 11654번 아스키 코드 파이썬(Python) (0) | 2019.11.11 |
백준 8958번 OX퀴즈 파이썬(Python) (0) | 2019.11.11 |
백준 2884번 알람 시계 파이썬(Python) (0) | 2019.11.11 |
백준 10871번 X보다 작은 수 파이썬(Python) (0) | 2019.11.09 |
최근댓글