[1260번] DFS - DFS와 BFS with Python (★)

문제

 

내가 작성한 코드

from collections import deque
import sys
input = sys.stdin.readline

# N, M, V
n, m, v = map(int, input().split())
graph = [ [] for i in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
 
for i in graph:
    if not i:
        continue
    else:
        i = i.sort()

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end= ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start]= True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
visited = [False] * (n + 1)
dfs(graph, v, visited)
print()
visited = [False] * (n + 1)
bfs(graph, v, visited)

 

코드 설명

from collections import deque
import sys
input = sys.stdin.readline

> 큐를 사용하기 위해서 deque 모듈을 불러왔고, 빠른 데이터 입력을 위해서 sys 모듈을 불러왔습니다.

> input = sys.stdin.readline 코드는 데이터를 빠르게 입력할 수 있는 코드입니다.

 

n, m, v = map(int, input().split())
graph = [ [] for i in range(n+1)]

> n, m, v 변수는 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호를 의미하는 변수입니다.

> graph 변수는 정점끼리 연결된 그래프 정보를 의미하는 변수입니다.

> [ [] for i in range(n+ 1) ] 로 코드를 작성한 이유는 정점의 수는 1부터 시작하기 때문에 range(n + 1)로 기존의 길이보다 1을 추가해서 빈 리스트를 만들었습니다.

 

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

> 간선의 개수만큼 반복문을 진행하기 위해서 for문을 사용했습니다.

> a, b는 연결되는 정점을 의미하는 각 정점입니다.

> 여기부분에서 굉장히 에러가 많이 발생했습니다.

> 처음에 graph[a].append(b) 만 작성하고 아래 graph[b].append(a)는 작성하지 않았습니다.

> 이렇게 되면 단방향 그래프가 되는데 예제 입력 2에서 에러가 계속 발생하게 됩니다.

> 양방향 그래프를 만들어주기 위해서 graph[b].append(a) 코드를 추가로 작성을 해주었습니다.

 

for i in graph:
    if not i:
        continue
    else:
        i = i.sort()

> 예제 출력에서 보시면 각 정점에서의 출력이 오름차순으로 출력됨을 인지할 수 있습니다.

> 그러므로, 각 정점에서 연결된 정점들을 오름차순으로 정렬해주기 위해서 반복문 for문을 사용하였습니다.

 

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end= ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start]= True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

> 이 dfs, bfs 코드는 '이것이 코딩테스트다' 책에서 나온 코드를 그대로 외워서 작성했습니다. 이런건 외우는거 밖에 답이 없는거 같습니다 ㅜㅜ

 

visited = [False] * (n + 1)
dfs(graph, v, visited)
print()
visited = [False] * (n + 1)
bfs(graph, v, visited)

> 그 다음 visited 변수는 각 정점이 방문을 했으면 True로 바꿔주면서 갔던 곳을 다시 가지 않게 하기 위한 변수입니다.

> 또 여기서 에러가 발생한게 있습니다.

> print(dfs(graph, v, visited)) 로 코드를 작성하면 마지막에 None 이 출력되게 됩니다. 그 이유는 dfs 함수를 보시면 return 값이 존재하지 않기 때문에 그런거라고 합니다. 주의!!