BFS DFS 정복하기

 

각 문제 유형별 풀 방법 정리 1) 그래프의 모든 정점을 방문해야하는 문제 DFS, BFS 뭐든 상관없다. 편한걸 쓰면 된다.   2) 경로의 특징을 저장하는 문제 예시로 각 정점에 숫자가 있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제. 각각의 경로마다 그 특징을 저장해두어야하는 문제는 DFS를 사용한다.   3) 최단거리를 구하는 문제 미로찾기등 최단거리를 구하는 경우 BFS가 좋다. DFS로 경로를 탐색하면 처음 발견하는 해답이 최단거리가 아닐수도 있지만 BFS는 현재노드에서 가까운 곳부터 찾기 때문에 경로를 탐색시 먼저 찾아지는 해답이 곧 최단거리다.   4) 검색대상그래프가 많이 클때DFS가 좋다고한다.   5) 검색대상의 규모가 별로 크지않고 검색시작지점으로부터 원하는 대상이 별로 멀지 않으면 BFS 출처: https://duckracoon.tistory.com/entry/DFS%EC%99%80-BFS-%EA%B0%81%EA%B0%81-%EC%82%AC%EC%9A%A9%ED%95%98%EB%8A%94-%EA%B2%BD%EC%9A%B0

---

---

01. BFS DFS의 기본틀 코드                                                                                                                          

예제 문제

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

 

https://velog.io/@hamfan524/%EB%B0%B1%EC%A4%80-1260%EB%B2%88-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 1260번-(Python 파이썬) - Bfs, Dfs

 

위에 블로그를 보고 이론 감 익히기

# BOJ_1260
from collections import deque
import sys
read = sys.stdin.readline

# dfs 구현
def bfs(v):
    q = deque()
    q.append(v)
    visit_list[v] = 1
    while q:
        v = q.popleft()
        print(v, end=" ")
        for i in range(1, n + 1):
            if visit_list[i] == 0 and graph[v][i] == 1:
                q.append(i)
                visit_list[i] = 1

# DFS 구현
def dfs(v):
    visit_list2[v] = 1
    print(v, end=" ")
    for i in range(1, n + 1):
        if visit_list2[i] == 0 and graph[v][i] == 1:
            dfs(i)


# 메인 코드
# 정점의 갯수 n, 간선의 갯수 m, 시작점 v
n, m, v = map(int, read().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
visit_list = [0] * (n + 1)
visit_list2 = [0] * (n + 1)
for _ in range(m):
    a, b = map(int, read().split())
    graph[a][b] = graph[b][a] = 1

dfs(v)
print()
bfs(v)

 

 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

---

---

02. BFS 응용 - 최단거리 문제                                                                                                                

예제문제

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

DFS로 뻘짓한 코드

# DFS로 푼다.
def dfs(cur_x, cur_y, visited, move_count):
    visited[cur_x][cur_y] = True
    for i in range(4):
        next_x = cur_x + dx[i]
        next_y = cur_y + dy[i]
        if next_x <= -1 or next_x >=n or next_y <= -1 or next_y >= m:
            continue
        if not visited[next_x][next_y] and graph[next_x][next_y] == 1:
            if next_x == n - 1 and next_y == m - 1:
                return move_count
            move_count = dfs(next_x, next_y, visited, move_count + 1)
            min_move[next_x][next_y] = move_count
    return move_count

# 메인문
move_count = 0
answer = dfs(0, 0, visited, move_count)
print(min_move)
print(answer)

 

BFS로 푼 코드

# BOJ_2178
from collections import deque

# 최단거리 문제를 풀 때는 BFS로 푼다.
def bfs(graph):
    # (0,0) 에서 출발
    q = deque([(0, 0)])
    # 각 점에서의 최단거리를 나타낸다.
    visited = [[0] * m for _ in range(n)]
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    visited[0][0] = 1
    graph[0][0] = 0
    while q:
        # print(q)
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]):
                if graph[nx][ny] == 1 and not visited[nx][ny]:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))
    answer = -1
    # 도착점에 이뤘을 때 0이 아니므로
    if visited[-1][-1]:
        # print(visited)
        return visited[-1][-1]
    return answer


# 입력
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
print(bfs(graph))

 

 

---

 

---

03. DFS 응용 - 연결 덩어리 문제                                                                                                         

 

1) 그래프의 모든 정점을 방문해야하는 문제 DFS, BFS 뭐든 상관없다. 편한걸 쓰면 된다.

 

 

예제문제

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

DFS 코드

# BOJ_2667
# dfs 구현
def dfs(x, y):
    global count
    if 0 > x or x >= len(graph) or 0 > y or y >= len(graph[0]):
        return False
    # 각 이동별로 dfs
    if graph[x][y] == 1:
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # house_count[-1] += 1
            # 그래프 내부의 점이면
            dfs(nx, ny)
        return True # 상하좌우 다 뻗으면 단지수를 하나 추가한다.
    return False


# 메인
n = int(input())
graph = [list(map(int, input())) for _ in range(n)]
# 각 단지내 집의 수를 저장한 리스트
house_count = []
# 이동 좌표 - 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
count = 0
# DFS 돌리기 - 모든 정점을 방문해야 한다.
for i in range(n):
    for j in range(n):
        if dfs(i, j):
            house_count.append(count)
            # print(house_count)
            count = 0

# 총 단지수와 각 단지내 집의 수 오름차순 출력
print(len(house_count))
house_count.sort()
for house in house_count:
    print(house)

 

BFS로 푼 코드

from collections import deque

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


def bfs(graph, a, b):
    n = len(graph)
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 0
    count = 1

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


n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

cnt = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            cnt.append(bfs(graph, i, j))

cnt.sort()
print(len(cnt))
for i in range(len(cnt)):
    print(cnt[i])

참고 블로그: https://hongcoding.tistory.com/71

 

 

예제:

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

DFS로 구현하게 되면 시간초과가 나오게된다.아래 처럼 sys.setrecursionlimit(10**6)을 따로설정해주면pypy3는 메모리 초과로 안되고python3에서 정답 코드로 매겨지게 된다.

# BOJ_10026
# 빨 초 파 각각 덩어리로 보는 갯수와
# 빨 = 초, 파를 각각 덩어리로 보는 갯수를 구하고 싶다.
# 1. 빨 초 파 각각 덩어리로 보는 갯수
# 색을 저장하고 같은 색이 모두 나올 때까지 돌리기
# 파란색 덩어리수는 같고, 빨 = 초만 다르게 구현해주면 된다.
# 애초에 색약 있을 때는 그래프에서 G부분을 R로 모두 바꿔준다.
import sys
sys.setrecursionlimit(10**6)

# dfs
def dfs(x, y, graph):
    global pre_color
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    # print(x, y, ':', graph[x][y], pre_color)
    # 지정 범위 내에 현재 컬러를 저장해둔다.
    tmp_color = graph[x][y]
    if graph[x][y] == pre_color and visited[x][y] == False:
        # 지나간 자리는 블랙으로 색칠해준다.
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            pre_color = tmp_color
            dfs(nx, ny, graph)
        return True
    return False


# 색을 판단해주는 함수
def add_color_chunk(x, y, graph):
    global red, green, blue
    if graph[x][y] == 'R':
        red += 1
        return
    elif graph[x][y] == 'G':
        green += 1
        return
    elif graph[x][y] == 'B':
        blue += 1
        return


# 입력
n = int(input())
graph_3color = [list(map(str, input())) for _ in range(n)]
# 각 칼라 구역의 갯수를 나타낸다.
red, green, blue = 0, 0, 0
# DFS에서 상하좌우 움직이기 위한 변수
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 방문했는지 보여준다.
visited = [[False] * n for _ in range(n)]
# 색약 없는 사람
for i in range(n):
    for j in range(n):
        pre_color = graph_3color[i][j]
        if dfs(i, j, graph_3color):
            add_color_chunk(i, j, graph_3color)
# print(red, green, blue)
print(red + green + blue, end=" ")


# 색약이 보는 그래프 만들어주기
# 색약 있는 사람(녹색을 빨간색으로 본다고 가정한다.)
graph_2color = graph_3color
for i in range(n):
    for j in range(n):
        if graph_2color[i][j] == 'G':
            graph_2color[i][j] = 'R'


# 각 칼라 구역의 갯수를 다시 리셋해준다.
red, green, blue = 0, 0, 0
# 방문 기록도 다시 리셋해준다.
visited = [[False] * n for _ in range(n)]
# 색약 있는 사람
for i in range(n):
    for j in range(n):
        pre_color = graph_2color[i][j]
        if dfs(i, j, graph_2color):
            add_color_chunk(i, j, graph_2color)
# print(red, green, blue)
print(red + green + blue)

 

이것을 BFS로 구현한다면

아래와 같다.단, 이 코드는 python3로는 시간초과가 뜨고,pypy3로는 정답 코드로 나오게 된다. 깔끔하다.왜 런타임 에러가 안 될까 최단거리 찾기 문제 말고도어떤 상황 때 DFS보다 BFS가 효율적일 수 있는 것일까.

from collections import deque


def bfs(x, y):
    queue.append((x, y))
    done.append((x, y))
    while queue:
        curr = queue.popleft()
        for i in range(4):
            nx = curr[0] + dx[i]
            ny = curr[1] + dy[i]
            if (0 <= nx < N) and (0 <= ny < N) and ((nx, ny) not in done):
                if colors[nx][ny] == colors[curr[0]][curr[1]]:
                    queue.append((nx, ny))
                    done.append((nx, ny))


N = int(input())
colors = [list(input()) for _ in range(N)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 정상인인 경우
queue = deque()
done = []
cnt_1 = 0
for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_1 += 1

# 적록색맹인 경우
for i in range(N):
    for j in range(N):
        if colors[i][j] == 'G':
            colors[i][j] = 'R'

queue = deque()
done = []
cnt_2 = 0
for i in range(N):
    for j in range(N):
        if (i, j) not in done:
            bfs(i, j)
            cnt_2 += 1

print(cnt_1, cnt_2)