[BOJ] 2665번 미로만들기 / 사용언어 : 파이썬(python)

※ 문제링크

2665번: 미로만들기

해당문제는 우선순위큐 자료구조와 BFS를 활용하여 풀 수 있는 문제였다. 최단거리를 구하는 것이 아닌 최대한 적게 방을 바꾸는 길을찾는 것이 문제의 조건이었기에 최소힙을 활용하여 문제를 해결하였다.  문제풀이방법에 대해 간단하게 설명하면, BFS함수를 통해 4방위를 탐색하고, 탐색할때마다 가중치도 함께 저장하여, 가장 작은 가중치부터 꺼내는 방식으로 길을 찾아서 배열의 마지막 지점에 도달하면 탐색을 종료하고, 결과값을 출력하면 문제를 해결할 수 있었다. 자세한 문제풀이방법과 코드는 아래와 같다.

1. 입력받은 값을 2차원 배열형태로 만들어 미로를 구현한다.

2. 특정좌표에서 4방위를 확인하고 탐색할 BFS함수를 작성하고, 최소힙을 이용하여 가중치가 작은 것부터 탐색을 할 수 있게한다.

3. 탐색 도중, 목표점에 도달하면 탐색을 중지하고 결과값을 출력해준다.

+ 함수를 작성할때 출발점에 대한 탐색또한 이루어지게 작성해야 오류가 뜨지 않는다.

+ n = 1, maze = [1]일때와 n = 1, maze = [0]일때 정상작동하는지 여부와 출발점이 검은색방으로 시작할 수 있음을 꼭 확인하자.

 

import sys
from heapq import heappush, heappop

n = int(input())
# n = int(sys.stdin.readline())
maze = []
for _ in range(n):
    maze.append(list(map(int, input())))
    # maze.append(list(map(int, sys.stdin.readline().rstrip())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False for _ in range(n)] for _ in range(n)]

def find_path(x, y):
    heap = []
    if maze[y][x] == 1:
        if n == 1:
            print(0)
            return
        heappush(heap, [0, x, y])
    if maze[y][x] == 0:
        if n == 1:
            print(1)
            return
        heappush(heap, [1, x, y])
    visited[y][x] = True

    while heap:
        btw, x, y = heappop(heap)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if maze[ny][nx] == 1 and visited[ny][nx] == False:
                    if ny == n-1 and nx == n-1:
                        print(btw)
                        return
                    visited[ny][nx] = True
                    heappush(heap, [btw, nx, ny])
                if maze[ny][nx] == 0 and visited[ny][nx] == False:
                    if ny == n-1 and nx == n-1:
                        print(btw+1)
                        return
                    visited[ny][nx] = True
                    heappush(heap, [btw+1, nx, ny])
find_path(0, 0)

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.