코딩테스트 준비 - 백준1260번 DFS와 BFS 풀이 (파이썬)

---

백준 1260번 풀이

---

문제풀러가기

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

DFS & BFS 알아보기

 

2021.06.11 - [코딩테스트/알고리즘] - (알고리즘)DFS(Depth-First-Search) 깊이 우선 탐색 - 파이썬

(알고리즘)DFS(Depth-First-Search) 깊이 우선 탐색 - 파이썬

2021.06.10 - [코딩테스트/알고리즘] - (알고리즘)BFS(Breadth-First-Search) 너비 우선 탐색 - 파이썬 + 백준 2178 풀이

(알고리즘)BFS(Breadth-First-Search) 너비 우선 탐색 - 파이썬 + 백준 2178 풀이

---

문제

---

코드

import sys
from collections import deque

N,M,V = map(int, sys.stdin.readline().split())
a_list = [[False]*(N+1)for i in range(N+1)] 
visited = [False]*(N+1)


for i in range(M):
    a, b =  map(int,sys.stdin.readline().split())
    a_list[a][b] = a_list[b][a] = True

print(visited)
print(a_list)
def dfs(x):
  if visited[x]==False:
    visited[x]=True
    print(x, end=" ")
    for i in range(1,N+1):
      if a_list[x][i]==True:
        dfs(i)

def bfs(x):
  queue = deque([x])
  visited[x]=False
  while queue:
    x=queue.popleft()
    print(x, end=" ")
    for i in range(1, N+1):
      if (visited[i]==True and a_list[x][i]==True):
        visited[i]=False
        queue.append(i)

dfs(V)
print()
bfs(V)

처음에 input()넣고 하니 계속 출력 초과가 떳습니다 ㅠ_ㅠ 

sys.stdin.readline()으로 하니까 되더라구요 ㅎㅎ

---

코드 풀이

  왼쪽 이미지의 예제 입력을 예로 코드를 풀이해보겠습니다.

코드설명 1-1

N=4, M=5, V=1일 경우,

N이 4라는건 1부터 4까지의 정점이 있다는 것입니다. 

코드설명 1-2

visited나 a_list를 만들때,False*N 이 아닌 False*(N+1)을 하는 이유는,

곱하기 N을 했을 경우, 만약 1을 방문했을때 표시를 visited[0]=True 로 해야됩니다. (1씩 빼준 인덱스를 넣어야되므로, 헷갈릴 수 있음)

하지만, M+1을 하면, 1을 방문했을때 표시를 visited[1]=True, 제일 큰 정점인 4를 방문했을때,

visited[4]=True를 해도 인덱스 범위에 벗어나지 않으며, 헷갈림을 방지할 수 있습니다. 

 

코드설명1-3

a_list[a][b] = a_list[b][a] =True

=> a_list[a][b] = True & a_list[b][a] = True 둘 다에 표시합니다. 

그 이유는, 예제 입력의 N,M,V외의 아래 입력 부분에서, (1,2), (1,3), (1,4)... 등 작은 숫자를 앞에다가 썼지만,

만약 큰 숫자가 앞에 나올 경우 예를 들어 (1,4)가 아닌 (4, 1)을 썼을 경우도 결국 결과는 같기 때문에, 둘 다에 표시해줘야 됩니다.

 

코드설명1-4

bfs(x)에서는 deque이 아닌 리스트를 써도 되지만, deque이 시간단축이 가능합니다. 

* deque을 쓸 때는 꼭 from collections import deque을 써줍니다. 

* deque을 썼을때만 popleft()가 사용 가능합니다.