[백준 2024/09/22] 2665번 미로 만들기 w. 0-1 BFS

1. 문제

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

 

2. 접근 방법

미로 만들기는 0-1 BFS를 적용할 수 있는 문제였다.

0-1 BFS에 알지 못했기에 이에 대해서 공부할 수 있던 좋은 기회였다. 실상은 BFS 보단 0-1, Dijkstra로 부르는 것이 더... 나을지도..?!

라는 생각이 들었다.

어떤 블로그에서 보았듯, 99% Dijkstra 에 1% BFS가 들어간 느낌이다.

https://velog.io/@vkdldjvkdnj/boj01261

[BOJ 1261] - 알고스팟 (0-1 BFS, Python)

 

0-1 BFS에 대해서 이해할 때, 위 블로그가 도움이 많이 되었다.

 

Dijkstra의 경우, list의 idx 번호에 따른 도시에, 인접 노드에 대한 정보를 포함하고 있었다.

하지만, 이번엔 2중 리스트의 각각의 idx가 도시를 나타낸다고 생각하면 풀기 좋다.

Dijkstra는 일반적으로, 

for w, i, j in range(self.g[u])

로 인접 노드에 접근하였다면, 이번에는

w, i, j = dq.popleft()
udlr = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for l, r in udlr:
	if 0 <= i+l < n and 0 <= j+r < n:
    ...

왼쪽, 오른쪽, 위, 아래가 인접 노드일 것이므로 이에 대한 범위 check와 더불어서 가중치 check도 하였다.

 

2중 리스트로 구성이 되어 있어 노드(도시)가 어떤 식으로 구성 되어 있는지 이해가 잘 되지 않았기에, 이를 그림으로 그려 보았다.

위와 같이 도시가 접근되게 된다.

 

visited list의 유무에 대해서도 생각해 보았는데, 다시 돌아간다면, cost 함수에 저장되어 있는 최솟값보다 큰 수를 지니고 있게 될 것이므로 continue가 되게 된다.

 

따라서 deque를 만들고, (w, i, j) 순으로 값을 넣어주니 좋았다. [0][0]에서 미로 탐색을 시작하므로, 

deque([(0, 0, 0)]) 를 통해 시작 점을 잡아줄 수 있도록 하였다. 더불어서, cost[0][0]도 0으로 선언해 주었다.

새롭게 접근하게 되는 노드의 가중치를 파악하고, 만약 1의 가중치를 지니고 있다면, deque의 뒤에 넣어서 최대한 나중에 접근할 수 있도록 하였다.

 

만약, 0의 가중치를 가진 노드에 접근하게 된다면, deque의 popleft를 통해서 먼저 접근할 수 있도록 하였다.

먼저 접근하는 것의 의의는, 노드를 빠르게 최단 경로로 수정할 수 있다는 점이다.

최단 경로로 수정하게 된다면, 

            if self.cost[i][j] < w:
                continue

위 조건문에서, 추후에 나오게 되는 수정 경로에 대해서 빠르게 pass 할 수 있기 때문에 시간복잡도에 도움을 준다.

 

3. 코드

import sys
from collections import deque

class Maze:
    def __init__(self, n):
        self.n = n
        self.cost = [[sys.maxsize] * n for i in range(n)]
        self.cost[0][0] = 0
        self.g = []

        for i in range(n):
            c = list(map(int, input()))
            self.g.append(c)

    def dij(self):
        dq = deque([(0, 0, 0)])
        udlr = [(-1, 0), (1, 0), (0, 1), (0, -1)]

        while dq:
            w, i, j = dq.popleft()

            if self.cost[i][j] < w:
                continue

            for l, r in udlr:
                if 0 <= i+l < n and 0 <= j+r < n:
                    if self.g[i+l][j+r] == 0:
                        renew_cost = self.cost[i][j] + 1
                        if self.cost[i+l][j+r] > renew_cost:
                            self.cost[i+l][j+r] = renew_cost
                            dq.append((renew_cost, i+l, j+r))

                    else:
                        if self.cost[i+l][j+r] > self.cost[i][j]:
                            self.cost[i+l][j+r] = self.cost[i][j]
                            dq.appendleft((self.cost[i+l][j+r], i+l, j+r))

        return self.cost[-1][-1]


if __name__ == "__main__":
    n = int(input())
    maze = Maze(n)
    print(maze.dij())