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

아래와 같은 정사각형방이 있을 때, 좌측상단 모서리에서 우측하단 모서리까지 가야한다.

이때 까맣게 색칠된 방은 0으로 표시되며, 이 방을 지나갈때는 1만큼의 비용이 발생한다.

좌측상단에서 우측하단에 도착할 수 있는 최소비용을 구하는 문제이다. 한 변의 길이 N은 1 이상 50이하이고, 실행 제한시간은 1초이다.

 

까만방 0, 흰방 1

 

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

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

그렇지만 우리 문제는 어떤 경로를 사용했는지가 중요한 문제가 아니라서 황급히 우선순위큐를 사용한 다익스트라로 구현을 바꾸었다.

 

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

 

import heapq

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

def count_corner_cost(N, map):
    mcost = 0
    if map[0][N-1] == BLACK:
        mcost -= 1
    for i in range(N):
        if map[0][i] == BLACK:
            mcost += 1
        if map[i][N-1] == BLACK:
            mcost += 1
    return mcost

def find_min_cost(N, map):
    mcost = 2 * N - 3 # 시작점 끝점은 무조건 흰 방이므로, 둘을 제외한 모든 방이 검은방인 경우가 최악의 경우이다.
    visited = [[False] * N for _ in range(N)]

    def bfs(init_r, init_c):
        nonlocal mcost
        q = [(0, init_r, init_c)]

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

            # 종료조건
            if cost >= mcost:
                # 이제 우선순위큐에는 현재 찾은 경로보다 비효율적인 경로만 존재한다.
                return mcost
            
            # 방문할 필요가 없는 경우
            if visited[r][c]:
                # ** WARN **
                # 노드를 큐에 추가하기 전에 방문확인을 해줬대도, 
                # 그 사이에 우선순위 높은 노드 방문하면서 이 노드를 처리하게 될 수도 있다. 
                # 그리고 그 경우가 꽤 많다.
                continue
            
            # 방문처리
            if r == N-1 and c == N-1:
                # print('끝점 도달, 비용 갱신')
                mcost = min(cost, mcost)
                if mcost == 0:
                    return 0 # 음의 비용을 갖는 경로는 절대 나타나지 않는다.
                continue

            visited[r][c] = True
            if map[r][c] == BLACK:
                cost += 1

            # 다음 노드 예약
            # 이때 흰방을 먼저 방문하도록한다.
            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]]]
            next_coor.sort(key = lambda x : map[x[0]][x[1]], reverse = True) # 흰방이 '1', 검은방이 '0'이라 순서를 뒤집어줘야 흰방이 앞으로 간다.
            for coor in next_coor:
                heapq.heappush(q, (cost, coor[0], coor[1]))

    bfs(0,0)
    return mcost

# 백준 입출력
N = int(input())
map = [input() for _ in range(N)]
print(find_min_cost(N, map))

 

 

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

 

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) 특정 조건을 만족하는 경로의 경우의 수를 구해야한다.