[BOJ] 2178번 미로 탐색 / 사용언어 : 파이썬(python)

※ 문제링크

2667번: 단지번호붙이기

해당 문제는 BFS를 활용하여 풀 수 있는 문제였다. DFS를 메모이제이션을 활용하여 기록하면서 풀면 답을 구할 수는 있으나, 시간 및메모리가 과도하게 사용되기에 BFS로 해결하기로 생각하였다. 문제조건 중 무조건 탈출이 가능하다는 전제조건이 주어졌기에 BFS함수를 작성하고 시작점에서 함수를 한번만 실행하는 방식으로 해결하였다. 자세한 문제풀이방법과 코드는 아래와 같다.

1. 입력받은 값을 2차원 배열로 변환하여 준다.

2. 파이썬 내장함수인 deque를 활용하여 BFS를 활용한 문제 해결코드를 작성한다.

3. 메모리 절감을 위해 마지막 지점에 도달하면 함수를 종료해준다.

+ sys 함수를 이용하여 시간을 좀 더 단축하였으며, sys함수 사용시에는 반드시 개행문자 처리를 해주도록 해야한다.

+ 중간에 미로의 특정점에 도달하기까지의 최솟값을 보기 위해 print문을 작성해서 확인하였다.

+ 배열에서 수학에서 쓰는 x,y 좌표점과는 반대로 적용된다는 점을 유념하여 작성하였다.(indexerror의 주요 원인)

 

from collections import deque
import sys

N, M = map(int, input().split()) # N: 행의 수(y좌표) / M: 열의 수(x좌표)
maze = []
for _ in range(N):
    maze.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 2

def bfs(maze, x, y, cnt):
    queue = deque()
    if maze[y][x] == 1:
        maze[y][x] = cnt
        queue.append([x, y])

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            cnt = maze[y][x]
            if 0 <= nx < M and 0 <= ny < N:
                if maze[ny][nx] == 1 and [nx, ny] == [M-1, N-1]:
                    maze[ny][nx] = cnt + 1
                    # print(cnt)
                    # for i in range(N):
                    #     print(maze[i])
                    # print('')
                    return
                elif maze[ny][nx] == 1:
                    # print(cnt)
                    # for i in range(N):
                    #     print(maze[i])
                    # print('')
                    maze[ny][nx] = cnt + 1
                    queue.append([nx, ny])
bfs(maze, 0, 0, cnt)
for i in range(N):
    print(maze[i])
print(maze[N-1][M-1] - 1)

 

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