[BOJ] DFS와 BFS


  • BOJ의 DFS와BFS 문제 풀이입니다

문제 풀이

  • 우선 입력을 받고 해당 그래프의 연결 관계를 행렬로 나타내 줍니다
  • 이 때 N+1의 크기의 행렬을 만들어서 입력 값의 노드 번호와 행렬의 인덱스를 같도록 만들어줍니다
import sys

N, M, V = map(int, sys.stdin.readline().split())
matrix = [[0]*(N+1) for _ in range(N+1)]


for _ in range(M):
    node1, node2 = map(int, sys.stdin.readline().split())
    matrix[node1][node2] = 1
    matrix[node2][node1] = 1

DFS

  • DFS는 stack을 사용해서 풀 수 있지만 재귀함수를 사용해서 풀 수 있습니다

  • 방문을 확인하기 위한 visited라는 리스트를 만들어줍니다

  • 그리고 반복문을 통해 해당 정점과 연결되어 있고 아직 방분하지 않은 정점을 찾습니다

  • 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다라는 조건이 있는데, 반복문을 통해 그래프의 인덱스를 1부터 시작하면 자연스럽게 정점 번호가 작은 것을 먼저 선택하게 됩니다

visited = [0 for _ in range(N+1)]
def dfs(matrix, V):
    visited[V] = 1
    print(V, end=" ")
    for i in range(1, N+1):
        if(matrix[i][V] == 1 and visited[i] == 0):
            dfs(matrix,i)

  • BFS

  • BFS는 queue를 사용해서 문제를 해결해줍니다

  • queuep에 노드를 넣어주고, 방문 처리를 위해 만든 visited 리스트에 방문 표시를 위해 1로 값을 정해줍니다

  • 그리고 반복문을 통해 해당 노드와 연결되어 있고 방문하지 않은 정점을 리스트에 추가해줍니다

  • 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다라는 조건이 있는데, 반복문을 통해 그래프의 인덱스를 1부터 시작하면 자연스럽게 정점 번호가 작은 것을 먼저 선택하게 됩니다

  • queue가 비어있는 경우는 모든 노드를 탐색한 경우이므로 이 때 반복을 끝내줍니다

def bfs(matrix, V):
    visited = [0 for _ in range(N+1)]
    queue = [V]
    visited[V] = 1
    while(queue):
        V = queue.pop(0)
        print(V, end=" ")
        for i in range(1, N+1):
            if(matrix[i][V] == 1 and visited[i] == 0):
                queue.append(i)
                visited[i] = 1


전체 코드

import sys

N, M, V = map(int, sys.stdin.readline().split())
matrix = [[0]*(N+1) for _ in range(N+1)]


for _ in range(M):
    node1, node2 = map(int, sys.stdin.readline().split())
    matrix[node1][node2] = 1
    matrix[node2][node1] = 1

def bfs(matrix, V):
    visited = [0 for _ in range(N+1)]
    queue = [V]
    visited[V] = 1
    while(queue):
        V = queue.pop(0)
        print(V, end=" ")
        for i in range(1, N+1):
            if(matrix[i][V] == 1 and visited[i] == 0):
                queue.append(i)
                visited[i] = 1

visited = [0 for _ in range(N+1)]
def dfs(matrix, V):
    visited[V] = 1
    print(V, end=" ")
    for i in range(1, N+1):
        if(matrix[i][V] == 1 and visited[i] == 0):
            dfs(matrix,i)



dfs(matrix, V)
print()
bfs(matrix, V)

Reference









© 2020. by dkmqflx

Powered by dkmqflx