[BOJ 백준] - DFS와 BFS 1260 Python

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

---

인접행렬 혹인 인접리스트를 이용해서 그래프를 탐색하는 방법을 아는지 묻는 문제이다. 인접행렬을 이용해서 풀어봤다.

일단 인접행렬을 구성해야 한다.
m개 간선이 있으므로 m번 반복하며 간선정보를 입력받고 입력받은 간선을 양방향으로 인접행렬에 설정해준다.

adj_arr = [[0] * (n+1) for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    adj_arr[a][b] = 1
    adj_arr[b][a] = 1

이제 DFS부터 탐색을 시작한다.

• 탐색을 시작할 정점의 번호를 매개변수로 받는다.
• 매개변수로 받은 정점은 탐색되므로 visited에 표시한다.
• 탐색된 정점에서 이동가능한 정점을 간선정보를 갖는 인접행렬에서 찾는다.
  • 인접행렬에서 이동가능한 정점을 찾았다면 visited로 방문되었는지를 체크한다.
• 현재 정점에서 이동가능한 정점이고 방문되지 않았다면 다음 정점을 start로 재귀호출한다.

def dfs(v):
    visited[v] = 1
    print(v, end = ' ')
    for i in range(1, n+1):
        if adj[v][i] == 1 and visited[i] == 0:
            dfs(i)

다음은 BFS 부분이다.

• 동일하게 매개변수로 탐색을 시작할 정점의 번호를 받는다.
• 시작하는 정점의 번호를 큐에 넣고 탐색을 시작한다.
  • 큐에 들어가는 순간 반드시 탐색되는 정점이므로 visited에 체크한다.
  • 탐색은 큐가 빌 때까지 즉 현재 정점에서 더이상 이동을 정점이 없을 때까지 반복한다.
• 매 반복마다 큐에서 정점을 하나 뽑고 뽑은 정점에서 이동가능한 정점을 찾는다.
  • 찾을 때는 인접행렬과 visited를 이용한다.
• 현재 정점에서 이동가능한 정점을 찾았다면 큐에 넣고 해당 정점은 앞으로 반드시 방문될 것이므로 visited에 체크한다.
  

def bfs(start):
    q = [start]
    visited[start] = 1

    while(q):
        v = q.pop(0)
        print(v, end=' ')
        for i in range(1, n+1):
            if adj[v][i] == 1 and visited[i] == 0:
                q.append(i)
                visited[i] = 1           

전체코드

def dfs(v):
   visited[v] = 1
   print(v, end = ' ')
   for i in range(1, n+1):
       if adj[v][i] == 1 and visited[i] == 0:
           dfs(i)

def bfs(start):
   q = [start]
   visited[start] = 1

   while(q):
       v = q.pop(0)
       print(v, end=' ')
       for i in range(1, n+1):
           if adj[v][i] == 1 and visited[i] == 0:
               q.append(i)
               visited[i] = 1

n, m, v = map(int, input().split())
adj = [[0] * (n + 1) for _ in range(n + 1)]
visited = [0] * (n+1)
for i in range(m):
   a, b = map(int, input().split())
   # 양방향
   adj[a][b] = 1
   adj[b][a] = 1

dfs(v)
visited = [0] * (n+1)
print()
bfs(v)