DFS, BFS

DFS, BFS 문제 유형 

DFS, BFS 기본형 // 

DFS - 완전탐색, 백트래킹 // BFS - 최단경로, 완전탐색

Dijkstra - 출발 노드에서 모든 노드간의 최단경로, cost가 음수일 경우 사이클이 없어야함

from collections import deque
import sys

sys.setrecursionlimit(10000)
input = sys.stdin.readline
V, E = map(int, input().split())
graph = [[] for _ in range(V)]
for _ in range(E):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
visit = [0] * V

def DFS(start):
    visit[start] = 1
    queue = deque()
    queue.append(start)
    while queue:
        x = queue.pop()
        for g in graph[x]:
            if not visit[g]:
                visit[g] =1
                queue.append(g)

def BFS(start):
    queue = deque()
    queue.append(start)
    visit[start] = 1
    while queue:
        x = queue.popleft()
        for g in graph[x]:
            if not visit[g]:
                visit[g] = 1
                queue.append(g)

cnt = 0
for i in range(V):
    if not visit[i]:
        DFS(i)
        BFS(i)
        cnt += 1

 

1. 구분된 구역 찾기

2차원 배열을 map으로 할때 -> dx, dy와 0<= nx,ny <N 조건으로 탐색

전체 map 에서 BFS 를 동작하되, BFS 동작시 주변영역을 모두 visted로 바꾼다.

BFS 동작 횟수를 덩어리의 갯수로 출력

  

N, M = input().split()
graph = [list(map(int, input())) for x in range(int(N))]
print(graph)
cnt = 0
def dfs(x, y):      # 전방향 모두 탐색
    global cnt
    if 0 <= x <= int(N)-1 and 0 <= y <= int(M)-1:
        if graph[x][y] == 0:
            graph[x][y] = 1
            dfs(x - 1, y)
            dfs(x, y - 1)
            dfs(x + 1, y)
            dfs(x, y + 1)
        else :
            return False
        return True
    else:
        return False
for j in range(int(N)): # 모든 지점 탐색
    for k in range(int(M)):
        if dfs(j, k) ==True:
            cnt +=1

 

2. 미로 길찾기

start와 end가 주어질때, start 에서 BFS 동작

모든 지점에서 이동 cost가 1로 동일하므로 직선 경로가 돌아가는 경로보다 항상 최단거리가 됨 (Dijkstra 불필요)

5 6
				# 미로 길찾기 문제
101010
111111
000001
111111
111111

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if graph[ny][nx] == 1:
                    graph[ny][nx] = graph[y][x] + 1
                    queue.append((nx, ny))
    return graph[n-1][m-1]


print(bfs(0, 0))

 

3. BFS으로 최소 길이 탐색 , DFS 와 BFS 차이점 / 백준 1697

DFS 는 한쪽방향을 끝까지 탐색후 되돌아오기 -> 경로가 여러개일경우 모든 경로의 길이를 확인한다면 BFS와 동일함

BFS 는 모든방향으로 탐색하면서 최소거리 찾기 -> 최단경로 찾은후 종료할경우 DFS보다 평균적으로 효율적이다

from collections import deque
import sys

sys.setrecursionlimit(10 * 6)

N, M = map(int, input().split())
queue = deque()
point = [0] * 100001


def BFS(start):
    queue.append(start)

    while queue:
        pre = queue.popleft()
        if pre == M:
            return point[pre]
        for present in [pre - 1, pre + 1, pre * 2]:
            if 0 <= present <= 10 ** 5 and not point[present]:
                point[present] = point[pre] + 1
                queue.append(present)


print(BFS(N))

 

 

출처 : 

https://velog.io/@suzieep/Algorithm-%EC%9D%B4%EC%BD%94%ED%85%8C-%EA%B2%8C%EC%9E%84-%EA%B0%9C%EB%B0%9C-%ED%8C%8C%EC%9D%B4%EC%8D%AC

https://hanco.tistory.com/37