[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)