깊이우선 탐색(DFS), 너비우선 탐색(BFS)

깊이우선 탐색(DFS)

Depth First Search의 약자로 넓이 우선 탐색을 의미

하나의 경우에 수에 대하여 모든 경우의 수를 조사, 다음 경우의 수를 조사하면서 해를 찾는 과정

 

이 트리를 기준으로 그림판으로 그림을 그려봄

 

A를 시작으로 B에 대한 DFS를 작동

 

B에서 파생된 [E,F] 에 대하여 [E]에 대해서 DFS작동

 

E 에서 파생된건 J이며 J안에는 아무것도 없고, E에서도 다른 길이 없으므로 재귀방식으로 돌아가

 

B에서 파생된 [E,F] 중 F에 대해서 DFS 작동

 

F에서 파생된 [K,L] 중 K에 대한 DFS 작동 

이런식으로 계속 움직여서 내가 원하는 값이 나오거나 끝날떄 까지 작동하게 만드는것이 DFS다

 

대표적인 문제: https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

import sys
input = sys.stdin.readline

dx = [-1,1,0,0]
dy = [0,0,-1,1]
def dfs(x,y):
    matrix[x][y] = 0

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if matrix[nx][ny] == 1:
                dfs(nx,ny)



TC=int(input())
for _ in range(TC):
    n,m,k = map(int,input().split())

    matrix = [[0]*m for i in range(n)]

    cnt = 0
    for __ in range(k):
        a,b = map(int,input().split())
        matrix[a][b] = 1

    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                dfs(i,j)
                cnt += 1
    print(cnt)

만약 이러한 문제를 dfs로 풀 경우의 수업 내용

 

이동이 가능한지에 대한 내용이 너무 길고 복잡하며 보기 안좋기 떄문에 위의 예제처럼 

dx, dy를 설정 후 for in문을 돌리면 보기에 좋을 것이다.

 

 

 

BFS란 Breadth First Search 의 약자 넓이 우선 탐색을 의미

하나의 경우의 수에 대한 다음 단게의 모든 경우의 수를 조사하면서 해를 찾는 과정

 

간단하게 설명해서

A라는 큐에 [B,C,D] 가 파생이 된다면

B,C,D 에 대한 검사를 진행해서 만약 정답이 아니라면

B,C,D에 대한 BFS를 실행

B안에 있는 [E,F] 에 대한 BFS를 실행

답이 아니라면 C에 대한 정답에 대한 BFS를 실행 하고 정답이니 True를 반환

 

대표 문제

1 에  파생된 [2,5,6] 에 대한 bfs실행

[2,5,6] 중 [2] = [3,11] 실행, [5] = [6(이미실행),9,11] [6] = [3,5(이미실행),12] 이므로

최소 거리는 [1,6,12] 이므로 두번이다.

 

예시 문제:https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

최소 거리를 구할떈 BFS구하는게 가장 효율이 좋다.

n,m=map(int,input().split())

s=[list(input()) for i in range(n)]

nx=[-1,1,0,0]
ny=[0,0,-1,1]

visited=[[0,0]]
s[0][0] = 1


while visited:
    a,b=visited[0][0],visited[0][1]

    del visited[0]

    for i in range(4):
        xx=a+nx[i]
        yy=b+ny[i]
        if n > xx >= 0 and m > yy >= 0:
            if s[xx][yy] == '1':
                visited.append([xx,yy])
                s[xx][yy] = s[a][b] + 1
print(s[n-1][m-1])

 

보통 Queue 안에 담아서 하는게 정석