문제
내가 작성한 코드
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 값이 존재하지 않기 때문에 그런거라고 합니다. 주의!!
'Coding > 백준' 카테고리의 다른 글
| [20291번] 파일 정리 with Python (0) | 2022.07.28 |
|---|---|
| [9663번] n-Queen with Python (★) (0) | 2022.07.27 |
| [15651번] N과 M (3) with Python (0) | 2022.07.26 |
| [15650번] 백트래킹 - N과 M(2) with Python (★) (0) | 2022.07.26 |
| [15649번] 백 트래킹 - N과 M(1) with Python (★) (0) | 2022.07.26 |
