[알고리즘] 크래프톤 정글 2주차 / 알고리즘 中 혼자서 못 푼 문제 정리5(미로만들기)

BOJ 2665 미로 만들기

난이도 : (크래프톤 정글 기준) 중, (백준 난이도 기준) 골4

사용 알고리즘 or 자료 구조 : DFS / BFS

 

처음 생각한 풀이

처음 생각한 방법은 단순 BFS를 돌려서 최단 경로에서 뚫는 벽의 수가 답일 것이다! 라고 생각하여 구현했었지만, 다 하고 생각해보니 최단 경로는 벽의 수랑 관계 없다는 것을 깨닫고 코드를 갈아엎었다.

 

두번째 생각한 방법은 도착점까지 모든 경로에서 뚫는 벽의 수를 비교해서 최솟값을 구하는 방식이었는데 당연하게도 모든 경로의 수를 세면 경우의 수가 기하급수적으로 많아져 deque를 써도 메모리가 터질 정도로 데이터가 저장되어 데이터 초과가 떠서 오답 처리가 되었다.

 

사실 지금 생각해보면 조금만 더 곰곰히 생각해봤다면 충분히 구현 가능할 만한 난이도이기도 하고 아이디어가 그렇게 어렵진 않았기에 구글링을 통해 접근법을 살펴본 것이 후회되지만... 그때 당시에는 '왜 안되지'라는 생각에 사로잡혀있었기 때문에 어쩔 수 없었던 선택이었던 것 같다.

구글링 이후 풀이

접근법 자체는 굉장히 단순했다.

 

총 두가지 접근법이 존재하는데 첫번째는 bfs를 실행할 때 사용하는 visited 배열을 True, False만 저장하는 형태로 쓰는 것이 아닌, 그 점까지 도착하는데 뚫은 벽의 수를 저장하여 그 전 위치에서 이동해올때의 개수와 원래 저장되어있는 개수를 비교하여 더 작은 값을 선택하는 방식으로 푸는 방법이다.

쉽게 말하자면 도착 지점에 벽이 있다면 visited[nx][ny] 와 visited[cx][cy] + 1을 비교하여 더 작은 값을 고르는 것이고, 벽이 없는 경우에도 visited[nx][ny]와 visited[cx][cy]를 비교하여 더 작은 값을 고르며 나아가는 방법이다.

 

두번째는 heapq를 사용하는 방법이다.

아이디어는 벽이 없는 지점을 우선순위로 탐색하여 뚫은 벽의 개수가 작은 지점들을 우선시하여 탐색하는 방법이다.

heapq에 첫번째 요소를 뚫은 벽의 개수, 두번째에 도착한 지점의 좌표를 저장하여 벽의 개수가 작은 것이 먼저 튀어나오도록 하여 푸는 방법이다.

문제의 예제를 통해 설명하자면 0,0 에서 출발하면 근처의 1인 지점들을 먼저 탐색하고 끝나고 나서야 벽을 1개 뚫은 지점을 탐색하게 된다. 그 이후의 과정도 bfs를 진행하며 cost가 작은 지점들은 먼저 탐색하는 방식으로 진행이 된다.

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

코드

import sys

import heapq

def bfs(x, y):

    global MIN

    hq = []

    heapq.heappush(hq, [0, x, y])

    visited[x][y] = True

    while len(hq):

        cost, cx, cy = heapq.heappop(hq)

        if cx == N - 1 and cy == N - 1:

            MIN = cost

            break

        for i in range(4):

            nx = cx + dx[i]

            ny = cy + dy[i]

            if 0 <= nx < N and 0 <= ny < N:

                if visited[nx][ny] == False:

                    if maze[nx][ny] == '1':

                        heapq.heappush(hq, [cost, nx, ny])

                    else:

                        heapq.heappush(hq, [cost + 1, nx, ny])

                    visited[nx][ny] = True

N = int(sys.stdin.readline())

maze = [list(str(sys.stdin.readline().strip())) for _ in range(N)]

visited = [[False for _ in range(N)] for _ in range(N)]

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

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

MIN = 999999999999

bfs(0, 0)

print(MIN)