2/6 Coding Test

✅ Coding Test

🎈 1261 알고스팟

미로 크기는 NXM이고 각 한 칸은 방으로 구성되어 있다. 미로는 빈 방 또는 벽으로 구성되어 있고 벽의 경우 부수고 이동해야 한다.

이동할 수 있는 칸은 상,하,좌,우 4방향이고 0,0에서 N,M으로 이동할 때 벽을 부수어야 하는 최소 개수를 구하는 문제.

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(m)]
# 벽 부순 횟수
visited = [[-1]*n for _ in range(m)]
# 상하좌우 4방향
dx = [-1, 1, 0, 0]
dy = [0 ,0 ,-1, 1]

queue = deque()
queue.append((0, 0))
visited[0][0] = 0

while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<m and 0<=ny<n:
            if visited[nx][ny] == -1:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y]
                    queue.appendleft((nx, ny))
                else:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))
print(visited[m-1][n-1])

< 해설 >

BFS를 이용한 풀이 방법.
1. deque 생성 후 시작점을 넣어주고 벽을 부순 횟수를 카운팅하는 visited 2차원 배열을 생성한 값에 초기 (0,0)의 값은 0으로 설정한다.
2. queue가 비지 않는 동안 주어진 범위 내 다음 과정을 반복한다.
2-1. 다음 위치가 방문하지 않은 곳이고, 빈 방인 경우 queue에 왼쪽에 삽입하고 이전 위치랑 값을 동일하게 설정한다.
2-2. 반대로 다음 위치가 벽인 경우 이전 값 + 1처리를 하고 큐에 오른쪽에 삽입한다.
3. 위 과정을 반복한다면 다음 위치가 방인 경우에 한해서만 큐가 계속해서 꺼내게 되고 결국 n,m 위치까지 이동하며 벽을 부순 횟수는 visited[m-1][n-1]이 된다.