[Python] DFS와 BFS

문제 1260

해당 문제 링크

정답

## DFS와 BFS

# 입력 변수 받기
N, M, V  = map(int, input().split())

# 인접 영행렬 생성
matrix = [[0] *(N+1) for i in range(N+1)]
    
# 방문한 곳 체크를 위한 배열 선언
visited=[0] * (N +1)

# 입력 받는 두 값에 대해 영행렬에 1 삽입
for i in range(M):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] =1

def dfs(v):
    # 방문한 곳은 1 넣기
    visited[v]=1

    print(v, end=' ')

    # 재귀 함수 선언 (start와 인접한 곳을 찾고 방문하지 않았다면 함수 실행)
    for i in range(1, N+1):
        if(visited[i]==0 and matrix[v][i]==1):
            dfs(i)


def bfs(v):
    # 방문해야 할 곳을 순서대로 넣을 큐
    queue=[v]

    # dfs를 완료한 visited 배열 (1로 되어있음)에서 방문 체크
    visited[v]=0

    # 큐 안에 데이터가 없을 때까지
    while queue:
        v=queue.pop(0)
        print(v, end=' ')
        for i in range(1, N+1):
            if(visited[i]==1 and matrix[v][i] ==1):
                queue.append(i)
                visited[i]=0


dfs(V)
print()
bfs(V)

참고 코드

풀이

예제 입력 1을 이용함.

코드를 하나씩 따라가보자

입력 변수를 받고, 인접 영행렬을 생성한다.
영행렬은 아래 그림과 같다.

방문한 곳 체크를 위한 배열 선언은 visited 변수명을 사용한다.

입력 받은 두 값을 영행렬에 맞게 1로 삽입

예제 입력에 따르면 아래와 같은 행렬이 만들어진다.
0 0 0 0 0
0 0 1 1 1
0 1 0 0 1
0 1 0 0 1
0 1 1 1 0

그럼 이제 DFS 돌릴 준비가 다 되었다.

DFS 코드를 보자

처음 탐색을 시작하려는 정점은 지정되어있다. 1을 먼저 방문하기 때문에 그에 맞게 방문한 곳에 1을 넣고, 출력한다.

for문을 보면,
방문하지 않은 곳을 보기 위해 visited[i]==0을 확인하고,
v와 인접하여 방문할 정점인지 보기 위해 matrix[v][i]==1을 확인한다.

방문하지 않았고, v와 인접하여 방문할 정점이라면,
재귀 함수로 dfs()함수를 더 들어간다.

예시 입력을 넣었다면, if(visited[2]==0 and matrix[1][2]==1)이 true이기 때문에
dfs(2)로 들어간다.
2 정점을 방문했으니 visited는 [0, 1, 0, 0, 0]에서 [0, 1, 1, 0, 0]이 된다.

다음 for문으로 2와 3은 인접해있지 않기 때문에 3은 넘기고, 2와 4가 인접하며, 4는 방문하지 않았기 때문에
다음 방문은 4정점이 된다.

그리고 남은 3 정점은 4와 인접해있기 때문에 다음 3을 방문하여 끝난다.

visited=[0, 1, 1, 1, 1] 로 정점1, 2, 3, 4를 모두 방문했다.

BFS 코드를 보자

이 상태 그대로 BFS로 넘어간다.
그리하여 bfs()함수에서는 방문 체크를 1로 하는 것이 아닌 0으로 한다.
visited[1]=0으로 처음 바꾸게 되어
visited=[0, 0, 1, 1, 1] 이 된다.

이때도, if(visited[2]==1 and matrix[1][2]==1)로
방문하지 않은 정점이면서, 인접해있다면 queue에 방문한 정점을 넣어준다.
최근에 방문한 정점을 큐에 넣어서 큐 안에 데이터가 없을 때까지 돌아간다.