99클럽 코테 스터디 15일차 TIL | 백준 미로만들기 풀이, 최소비용과 BFS

문제 바로가기 : https://www.acmicpc.net/problem/2665

 

그림과 같은 N x N 미로가 있다. 빈방은 흰색(1), 벽은 검은색(0)이다.
(0, 0)에서 시작해서 (n-1, n-1)로 가기 위해 최소 몇개의 벽을 뚫어야하는지 구하는 문제이다.

한 변의 길이 N은 1 이상 50이하이고, 실행 제한시간은 1초이다.

 

까만방 0, 흰방 1

 

처음에는 모든 경우의 수를 모두 돌아보되, 가능성이 없는 경로는 빠르게 쳐내기 위해 DFS로 빠르게 최소비용을 구하고자했었다.

쓸데없이 경로를 꼭 알아야한다고 생각을 했던것...

그렇지만 우리 문제는 어떤 경로를 사용했는지가 중요한 문제가 아니라서, BFS로 미로를 돌며 (0, 0)에서 임의의 (x, y)로 가려면 얼마의 비용이 드는지 구하는 것으로 방향을 틀었다.

 

전체 구현 코드는 아래와 같다.

 

from heapq import heappush, heappop

def min_cost(n, miro) -> int:
    visit = [[False] * n for _ in range(n)]
    min_cost = 2 * n
    START, END = (0, 0), (n-1, n-1)
    WHITE, BLACK = '1', '0'

    # 저렴한 경로부터 탐색하도록 도와줄 우선순위큐
    pq = [(0, START[0], START[1])] 
    
    # BFS 시작
    while len(pq) > 0:
        cost, r, c = heappop(pq)
        
        # 1. 방문할 필요가 있나 따져본다.
        if visit[r][c]:
            continue
        if cost > min_cost:
            continue # 이런 비싼 경로는 볼 가치도 없음

        # 2. 방문처리
        visit[r][c] = True
        # 2-1. END에 도달했다면 최소값 갱신
        if END == (r,c):
            min_cost = min(min_cost, cost)
            continue
        # 2-2. 아니라면 현재 비용만 갱신
        if miro[r][c] == BLACK:
            cost += 1

        # 3. 다음노드 추가
        next_rc = [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]
        for nr, nc in next_rc:
            if (nr in range(0, n)) and (nc in range(0, n)):
                heappush(pq, (cost, nr, nc))
    
    return min_cost

 

 

여기서 시간을 많이 단축시킬 수 있었던 아이디어들이 몇 있었다.

 

1. BFS로 바꾸고 visit 확인을 공유한것

 

원래는 모든 개별 경로를 확인하기 위해 아래처럼 방문 이력을 set으로 다 따로 관리했다.

def dfs(row, col, cost, visited: set):
	# 방문처리...
    dfs(next_row, next_col, next_cost, visited | {(row, col)})

그렇기 때문에 비효율이 엄청나게 심했다.

한변의 길이가 N일때 칸은 N * N 개이므로

 

- 시간복잡도 = 4 ^ (N * N)

- 공간복잡도 = N * N * 4 ^ (N * N)

 

이렇게 나와버리는 것이다... N = 20일때 연산이 1.5분씩 걸리곤 했다.

 

이걸 bfs로 바꿔주면 적어도 공간복잡도는 많이 아낄 수 있다.

visit = [[False] * N for _ in range(N)] # 공간복잡도가 O(N * N) 으로 획기적으로 감소
q = []
while len(q) > 0:
  	# 방문처리...

 

근데 이렇게한다고 최소비용을 찾는걸 보장할 수는 없다.

지도가 ㄹ자 모양으로 뚤려있는 5 x 5 지도를 생각해보면, 좀 돌더라도 ㄹ자로 가는 경로를 찾아내야하는데 꺾었다가 돌아올 때 이미 방문한 경로로 처리되서 무시당하기 때문이다.

 

2. 방문 노드에 우선순위 부여

우리가 눈으로 최소경로를 찾을 때 사용하는 우선순위를 그대로 사용했다.

 

1. 시선이 ↘️ 이 방향으로 향한다. -> 방향을 하우상좌 순서로 지정

2. 방문했던 곳을 또 가는 것은 의미가없다. -> 큐에 넣기 전에 visit 확인

3. 일단 흰칸을 먼저 방문한다. -> 큐에 넣기 전 노드 정렬

 

그리고 우리가 원하는 것은 (0,0)에서 각 점에 도달하기 위한 최소비용이다.

모든경로를 조사할게 아니라, 이걸 (k,k)에 가기위한 최소값을 구하는 문제로 나눠서 풀어야한다.

그래서 똑같이 (2,1)로 가는 경로라도, 더 비용이 적은 경로를 거친 애가 앞으로 나오게 하기 위해서 우선순위 큐를 활용했다.

dirs = [(1,0),(0,1),(-1,0),(0,-1)] # 조건 1. 하우상좌로 우선순위를 준다.

# bfs
while len(q) > 0:
	# 종료조건 확인 및 방문처리...
    
    # <큐 갱신>
    # 조건 2. 방문했던 노드는 스킵한다.
    next_coor = [(r+dir[0], c+dir[1]) for dir in dirs if r+dir[0] in range(N) and c+dir[1] in range(N) and not visited[r+dir[0]][c+dir[1]]]
    # 조건 3. 비용이 안드는 흰 방을 먼저 방문한다.
    next_coor.sort(key = lambda x : map[x[0]][x[1]], reverse = True) # 흰방이 '1', 검은방이 '0'이라 순서를 뒤집어줘야 흰방이 앞으로 간다.
    
    for coor in next_coor:
 		# 큐에 (cost=10, row=2, col=1)이 먼저 들어왔대도,
        # 나중에 (cost=1, row=2, col=1)이 추가되었다면 이걸 먼저 반환한다.
    	heapq.heappush(q, (cost, coor[0], coor[1]))

 

 

3. 탐색의 비효율 제거

사실상 우선순위 큐를 사용했기에 사용할 수 있던 전략이다.

 

재귀 + DFS를 사용했을 때는 최소값을 발견했더라도, 이미 재귀 트리가 넓게 펼쳐져있어서 함수가 다시 돌아오는데 한참 걸렸다.

그리고 그게 최소값임을 보장할 수도 없어서 바로 리턴하기도 힘들었다.

min_cost = 2 * N
def dfs(row, col, cost, visited: set):
	nonlocal min_cost
	
    if cost >= min_cost:
    	print("비용초과")
        return
    # ...

# N = 20쯤 해서 실행시켜보면 후반부에 "비용초과"가 몇백줄씩 출력된다. 너무 많아서 세보지도 못했다.

 

그러나 이제는 비용에 대해 우선순위큐가 정렬된 상태이다.

(cost = 10, row = 5, col = 5) 라는 노드가 튀어나왔고, (5, 5)가 끝점이라면

우선순위 큐에 남아있는 다른 노드들은 무조건 비용이 10 이상이라는 소리이므로 더 볼 필요도 없이 10을 반환하면 된다.

 

그리고 한 노드에 대해 비효율적으로 접근하는 경우도 걸러낼 수 있었다.

예전 방식이었으면 visited을 공유하지 않아서 (0,0) -> (1,1)을 비용 100을 내고 가는 바보같은 경우도 다 연산을 해줬어야하는데,

이제는 비용이 적게드는 경로(=흰방)를 최우선으로 탐색하기 때문에, 이미 방문한 경로라면 분명 지금 선택하는 방식보다 적은 비용으로 탐색을 했음을 보장할 수 있다.

while len(q) > 0:
    cost, r, c = heapq.heappop(q) # 비용이 적은 노드부터 탐색한다.

    # 종료조건
    if cost >= mcost:
        # 이제 우선순위큐에는 현재 찾은 경로보다 비효율적인 경로만 존재한다.
        return mcost

    # 방문할 필요가 없는 경우
    if visited[r][c]:
        # ** WARN **
        # 노드를 큐에 추가하기 전에 방문확인을 해줬대도, 
        # 그 사이에 우선순위 높은 노드 방문하면서 이 노드를 처리하게 될 수도 있다. 
        # 그리고 그 경우가 꽤 많다.
        continue

 

 

앞으로는 이미 지나온 경로를 특별히 관리할 필요가 없다면, 우선순위큐와 BFS를 활용한 다익스트라 전략을 가장 먼저 선택할 것 같다.

 

물론 아래 같은 경우는 어쩔수없이 방문 경로를 따로 관리해줄 것 같긴하다.

- ex) 경로를 무조건 한칸씩 띄워놓고 지나가야한다.

- ex) 특정 조건을 만족하는 경로의 경우의 수를 구해야한다.