Chapter 3. DFS & BFS Algorithm

알고리즘 스터디 3주차의 주제는 DFS와 BFS다.

DFS와 BFS란?

DFS와 BFS는 그래프를 탐색하는 방법이다. DFS는 Depth First Search, BFS는 Breadth First Search의 약자로서 말그대로 각각 깊이와 너비를 우선으로 그래프를 탐색하는 방법이다.

문제풀이

이번 주는 안전영역(실버 1), 미로탐색(실버 1), DFS와 BFS(실버 2)라는 문제들을 풀어보았다.

안전 영역(실버 1)

해당 문제는 아래 링크에서 풀어볼 수 있다.
https://www.acmicpc.net/problem/2468

입력받은 graph에서 가장 높은 높이를 찾아 mostHigh에 저장한다. 그리고 0(비가 아예 안오는 경우)부터 mostHigh-1(가장 높은 높이빼고 다 잠기는 경우)의 범위에서 for문을 통해 각 높이를 한 번씩 제공하며 해당 높이에 대해 안전 영역의 수를 찾는다.

전체코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
mostHigh = 0

for i in range(N):
    for j in range(N):
        if graph[i][j] > mostHigh:
            mostHigh = graph[i][j]

def bfs(mostHigh):
    answer = 0
    for level in range(0, mostHigh):
        visited = [[0] * N for _ in range(N)]
        safearea = 0
        for i in range(N):
            for j in range(N):
                if graph[i][j] > level and visited[i][j]==0:
                    queue = deque()
                    queue.append((i, j))
                    visited[i][j] = 1

                    while queue:
                        x, y = queue.popleft()

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

                            if 0<=nx<N and 0<=ny<N and graph[nx][ny] > level and visited[nx][ny]==0:
                                visited[nx][ny] = 1
                                queue.append((nx, ny))
                    safearea += 1

        if safearea > answer:
            answer = safearea
    return answer

print(bfs(mostHigh))

 

미로탐색(실버 1)

해당 문제는 아래 링크에서 풀어볼 수 있다.
https://www.acmicpc.net/problem/2178



현재 위치에서 상하좌우를 탐색한다. 이동할 수 있는 위치(graph[nx][ny]==1 이고 맵 밖을 벗어나지 않는 좌표)면 현재 위치에 저장되어 있는 값에 1을 더한 값을 이동할 위치에 저장하는 방식으로 해결했다.

전체 코드

import sys
from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(N)]

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

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

    while loc_queue:
        x, y = loc_queue.popleft()

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

            if 0<=nx<N and 0<=ny<M and graph[nx][ny]==1:

                loc_queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1
        
    return graph[N-1][M-1]


print(bfs(0, 0))
print(*graph, sep='\n')

 

DFS와 BFS(실버 2)

해당 문제는 아래 링크에서 풀어볼 수 있다.
https://www.acmicpc.net/problem/1260



각각 DFS와 BFS를 이용해 방문기록을 저장하는 배열을 통해 쉽게 해결할 수 있다.

전체 코드

import sys
from collections import deque

input = sys.stdin.readline

N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]

visited_dfs = [0]*(N+1)
visited_bfs = [0]*(N+1)

def dfs(graph, V, visited_dfs):
    visited_dfs[V] = 1
    print(V, end=' ')

    for next in graph[V]:
        if visited_dfs[next] == 0:
            dfs(graph, next, visited_dfs)

def bfs(graph, V, visited_bfs):
    queue = deque([V])
    visited_bfs[V] = 1

    while queue:
        now = queue.popleft()
        print(now, end=' ')
        
        for next in graph[now]:
            if visited_bfs[next] == 0:
                queue.append(next)
                visited_bfs[next] = 1

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

dfs(graph, V, visited_dfs)
print()
bfs(graph, V, visited_bfs)