DFS/BFS - 문제후기

밑에 한 30개 더있지만 클론코딩과 벡엔드도 해야 하기 때문에... 조금씩 나누어 푸는걸로..

DFS/BFS

---

DFS/BFS가 첫 번째 고비라고 들었던 것 같은데, 공부해보니 시간이 정말 정말 많이 들어서 이렇게 오래 걸려도 되나 싶은 개념이었다. 물론 많은 문제를 접하고, 이에 익숙해지면 어려움 없이 풀어갈 수 있을 것 이기에, 큰 두려움은 가지지 않았다.

 

DFS(깊이)와 BFS(넓이)의 작동원리, 출처: GIF http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

 

먼저 DFS(Depth First Search)란 다차원 배열 혹은 그래프에서 각 칸을 방문할때 깊이를 우선으로 탐색하는 알고리즘이다. 위의 gif에서도 알 수 있듯이, 각 top node에서부터 하나의 branch의 최하단까지 탐색하고 끝에 도달하면 다른 branch를 탐색한다. 

 

다음으로, BFS(Breadth First Search)란 BFS와 매우 유사한데, 다만, 각 칸을 방문할때, 하나의 branch에 끝에 도달하고 다른 branch를 탐색하는 것이 아닌, 최 상단 노드와 인접한 노드를 을 탐색하고, 또다시 탐색한 노드와 인접한 노드를 탐색하는 방식이 너비를 우선으로 한다고 하여 Breadth(너비) First(우선) Search(탐색)이라고 불린다. 

 

둘 다 장단점이 있지만, PS(Problem Solving)에서는 보통 BFS를 주로 쓰게 되는데, 그 이유는 PS에서는 보통 최단거리 측정(e.g 미로 탈출)과 같은 유형들이 단골 문제로 나오는데, BFS에서는 너비를 우선으로 탐색하므로, 각 노드가 서로 1만큼 떨어져 있어서 가장 마지막에 탐색되는 노드가 몇 번의 탐색을 거쳤는지만 알면 끝에 도달하기 위해서 얼마만큼 가야 하는지, 즉 거리를 알 수 있지만, DFS는 깊이 우선 탐색으로, 가장 마지막에 탐색하는 노드가 가장 멀리 떨어져 있고, 각 노드가 1만큼 떨어져 있다는 보장이 되지 않아서 최단거리 측정 문제에는 적합하지 않기 때문이다.

 

그렇기에 우리는 다차원배열에서 굳이 BFS대신 DFS를 쓸 이유가 없기 때문에, 다차원 배열 관점에서는 BFS를 주로 사용하게 되고 이번 문제집의 문제풀이도 모두 BFS로 진행하였기 때문에 그를 기반으로 설명할 것이다. 물론 DFS도 필요한 상황이 나중에는 나오게 될지도 모르겠지만 말이다... 

 

그렇다면 BFS는 어떻게 작동하는 것일까?

 

BFS 알고리즘 by baaaaarkingdog

BFS는 Queue라는 자료구조 (FIFO, 선입선출)를 이용하며, 기본적인 탐색흐름은 위에서 gif에서 보다시피 점점 퍼져나가는 듯한 흐름이다. 먼저 시작하는 칸의 좌표 (이차원 배열일 경우, (x, y)의 튜플 형태로 큐에 append 한다)를 append 하고 방문했다는 표시를 남긴다, 초기 값이 모두 0이라면, 1로 바꾸거나, 따로 똑같은 크기의 다차원 배열을 만들어서 거기에다 bool로 표시를 하던 상관은 없다, 무튼 탐색이 완료된 칸이라는 것만 표시할 수 있으면 된다. 그리고 그 칸(큐의 원소)을 꺼내서 상하좌우로 인접한 칸에 대해 탐색을 진행하는데 탐색을 하는 중, 이 칸이 이미 탐색된 칸이라면 continue 같은 걸로 넘어가고 아직 방문처리가 안된, 처음 오는 칸이라면 방문 표시를 하고, 그 칸을 큐에 append 한다.

 

이렇게 새로이 방문하는 칸을 계속 que에 넣고 상하좌우로 탐색을 하다가, 어느순간 queue가 비는 순간이 오는데, 이때는 바로 이제 더 이상 방문할 칸이 없다는 뜻이므로 탐색이 완료된 것이다. 

 

지금 보면 지극히 어려울 게 없는데, 왜 구현에서 이렇게 머리를 싸맸는지는 모르겠지만, 이제 정말 알고리즘 다운 알고리즘을 하나 또 습득한 것 같아서 기분이 좋았다. BFS/DFS 문제는 코테 단골 문제라니까 진짜 다양한 유형의 문제들을 많이 풀어봐야 할 것 같다.

 

(BOJ 2178) 미로 탐색

---

2178번: 미로 탐색

 

미로를 빠져나가는데 걸리는 거리를 측정하는 BFS의 가장 기본이 되는 문제이다. BFS의 구조와 동작을 구현 할 수 있고, 탐색하면서 누적 거리를 더해서 최종 거리를 출력할 수 있다면(...) 간단하게 풀 수 있는 문제이다. 

 

이 문제를 풀면서 배운점과 핵심 포인트라고 느낀 점은 바로,

 

배운 점:

 

1. BFS의 풀이에 사용되는 Queue는 from collections import deque를 사용한, Deque을 사용하자! -> deque의 popleft와 append는 일반 queue보다 시간 복잡도 면에서 우수하다. 

 

2. BFS의 구조는 정석적으로 정해져 있기 때문에, 그 틀을 체화시켜서 스스로 구조를 짜 본 건 이 문제를 풀 때가 처음인데, 그 틀을 이 문제를 기점으로 잘 익혔다. 

 

핵심 포인트:

 

1. BFS의 기본적인 틀을 잘 구현할 수 있는가? (상하좌우 탐색, 큐 다루기.. 등등)

 

2. 거리를 잘 축적하여 탈출시의 거리를 올바르게 return 해줄 수 있는가?

 

3. 이차원 배열의 입력을 잘 받을 수 있는가? 

 

정도이다.

 

1. deque는 다뤄본 적이 있어서, 그다지 어려움은 없었는데, 상하좌우 탐색을 머릿속에 각인시키는 것이 그나마 조금 시간이 걸렸다. index 배열 (e.g. [-1,1,0,0]) 을 이용하여 반복문을 4번 돌려서 현재 x, y 좌표에 더해서 nx, ny를 만드는 과정을 주저함 없이 코딩할 수 있어야 한다.

 

2. 이건 이 문제가 배열의 오른쪽 끝, 즉 (row, column)에 무조건 도달하도록 되어 있어서 생각보다 허무하게

graph [n-1][m-1]로 구현이 가능했지만, 만약 무조건 (row, column)에 도달하지 않도록 한다면, 이 차원 배열에서 max 메서드를 사용하면 되겠다는 생각을 했다.

 

3. 이건 별 문제는 아닌데, 이전까지 다차원 배열의 입력이 존재하는 PS 문제를 풀어보지 않아서 문제 풀기 전 살짝 망설였지만, 그냥 여러 원소를 한 줄에 입력받을 때와 같이 입력받고 이를 반복문으로 반복하면 [  [ a ], [ b ], [ c ]  ] 이런 식으로 들어가게 된다.

 

자세한 내용은 아래의 코드를 보도록 하자. 

 

import sys
from collections import deque

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 nx < 0 or ny < 0 or nx >= n or ny >= m: #외곽으로 벗어났는가?       
                continue

            if graph[nx][ny] == 0: #벽인가?
                continue

            if graph[nx][ny] == 1 and check[nx][ny] == 0: #갈수있는길이고, 방문처리가 아직 안되었다면!
                check[nx][ny] = 1 #방문처리
                graph[nx][ny] = graph[x][y] + 1 # 거리 측정
                queue.append((nx,ny)) # 다음 탐색을 위해 큐에 삽입
    
    return graph[n-1][m-1]

graph = []

dx = [-1,1,0,0] #상하좌우
dy = [0,0,-1,1]

n,m = map(int,sys.stdin.readline().split())

check = [[0]*m for _ in range(n)] #방문기록용 이차원 배열
 
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip())))


print(bfs(0,0))

 

(BOJ 4179) 불!

4179번: 불!

 

골드 티어의 BFS문제이다. 조금 난이도가 있는 문제이고, 실제로 엄청나게 고전했던 문제이다. 

 

문제를 간략하게 설명하자면, 지훈이가 일하는 미로에 불이 나서 탈출을 해야 하는데, 불과 지훈이는 매분마다 한 칸씩 이동할 수 있는 상황에서 지훈이가 탈출한다면 몇 분(몇 칸)만에, 출구로 가기 전에 불이 출구를 막아서 탈출할 수 없다면 IMPOSSIBLE을 출력해야 하는 문제이다.

 

풀면서 느낀 핵심 포인트는 아래와 같다.

 

1. 불이 번지는 거리를 기록한 배열의 BFS, 지훈이가 탈출하기 위해 움직이는 거리를 기록한 배열의 BFS, 이 두 개를 적절히 컨트롤하는 것이 이 문제의 관건이다.

 

2. 불은 지훈이와 관계없이 사방으로 퍼지기 때문에 일반적인 BFS로 진행 가능하지만, 지훈이는 불이 있는 곳에는 가지 못하고, 불이 출구를 막았다면 IMPOSSIBLE 출력이 나와야 하기 때문에 적절한 조건으로 컨트롤이 필요하다 ( 핵심 포인트 중의 핵심 포인트라고 생각한다)

 

3. 이는 BFS로 기록된 불의 이동거리를 참고하여 지훈이가 현재 위치에서 한 발자국 움직인 위치의 ( jihoon_dist [x][y] + 1 ) 불의 이동거리가 지훈이 보다 더 크다면 ( 이 위치에는 불이 아직 도착하지 않았다면 ) 이동할 수 있도록 처리했다. IMPOSSIBLE 처리는, 만약 지훈이가 벽과 불을 피해 올바르게 이동하다가, 그다음 이동할 좌표가 map을 벗어난다면 탈출할 수 있다는 의미이므로 그때 지훈이가 이동한 거리를 return 하고, 만약 불에 가로막혀 탈출할 수 없다면 map 밖으로 도달하기 전에 지훈이의 이동경로가 모두 막혀 (모두 방문처리되어 종료되는 BFS의 상황) queue의 while문이 종료될 것이므로 IMPOSSIBLE을 출력하도록 한다.

 

자세한 내용은 아래의 코드를 참조하자.

 

import sys
from collections import deque


def bfs(graph):
    fire = deque()
    jihoon = deque()

    for i in range(r):
        for j in range(c):
            if graph[i][j] == 'J':
                jihoon.append((i,j))
                jihoon_dist[i][j] = 1 #방문처리
            elif graph[i][j] == 'F':
                fire.append((i,j))
                fire_dist[i][j] = 1   #방문처리
    
    while fire:
        x,y = fire.popleft()
        for i in range(4):

            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < r and 0 <= ny < c:
                if not fire_dist[nx][ny] and graph[nx][ny] != '#':
                    fire.append((nx,ny))
                    fire_dist[nx][ny] = fire_dist[x][y] + 1
            

    while jihoon:

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

            
            if 0 <= nx < r and 0 <= ny < c:
                if not jihoon_dist[nx][ny] and graph[nx][ny] != '#':
                    if jihoon_dist[x][y]+1 < fire_dist[nx][ny] or not fire_dist[nx][ny] : # 지훈이의 현재좌표에서 한발짜국 갔을때 (+1) 불의 dist보다 작은가? or 불이 아직 번지지 않은곳인가? (0으로 초기화 했으므로..)
                        jihoon_dist[nx][ny] = jihoon_dist[x][y] + 1
                        jihoon.append((nx,ny))
            else:                  
                return jihoon_dist[x][y] 
    
    return "IMPOSSIBLE"


graph = []

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

r,c = map(int,sys.stdin.readline().split())
fire_dist = [[0]*c for _ in range(r)]
jihoon_dist = [[0]*c for _ in range(r)]

for i in range(r):
    graph.append(list(sys.stdin.readline().rstrip()))

print(bfs(graph))

 

마무리

---

점점 이제 일어나서 프로그래밍 공부를 하는 것이 익숙해져 간다. 이제 슬슬 알고리즘뿐만 아니라 백엔드 쪽 프로젝트도 진행해야 하는데 더 열심히 해야겠다... 힘내자!!