[BOJ] 1261. 알고스팟 (Python)

 

1261번: 알고스팟

 

오랜만에 푸는 벽 부수기 문제!

코테 준비를 하면서 제일 처음 벽 부수기 문제를 만났을 때는 머리 터지겠다.. 했는데

그래도 여러 BFS 문제를 풀어봐서인지 비교적 쉽게 풀 수 있었다!

 

BFS의 대표 유형과 비슷한데 알고스팟에서 유의해야할 점은 

"이미 지나간 곳이지만 더 적은 횟수로 벽을 부수고 지나갈 수 있는가?"라는 점이다!

더 적은 횟수로 벽을 부수고 지나갈 수 있다면 이미 방문한 곳이라도 다시 재방문을 해주어야 한다.

 

따라서 일반적으로 방문을 표시하는 visited 행렬에 True, False(또는 1, 0) 대신 몇 번 벽을 부수고 해당 칸에 도착했는지를 저장했다.

아직 방문 이전이면 -1, 한 번도 안부쉈으면 0, 한 번 부쉈으면 1, ...

 

운영진이 현재 위치에서 상하좌우로 살피면서 

1. 처음 방문하는 곳이면

   - 벽이 있으면 (현재 벽 부순 개수) + 1, 벽이 없으면 (현재 벽 부순 개수)

   - 큐에 넣기

2. 이미 방문한 적이 있으면

   - 벽 부순 개수를 비교해서 더 적은 경우에만 visited 업데이트 후 큐에 넣기

와 같이 방문하면 된다!

 

위 조건문만 정확하게 세우고 코딩에 들어가면 헷갈리지 않고 풀 수 있다.

 

 

from collections import deque

def solution(M, N, array) :
    visited = [[-1] * M for _ in range(N)]
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

    def check_pos(x, y) :
        if 0 <= x < N and 0 <= y < M :
            return True
        return False

    q = deque([(0, 0)])
    visited[0][0] = 0
    while q :
        x, y = q.popleft()
        for i in range(4) :
            nx, ny = x + dx[i], y + dy[i]
            if check_pos(nx, ny) :# 이동 가능한 경우
                # 이미 방문했으면
                if visited[nx][ny] != -1 :
                    if array[nx][ny] == 1 : # 벽이 있는 곳이면
                        # 기존에 알고 있던 벽 부순 개수 > 지금 방문했을 때 벽 부순 개수 + 1
                        if visited[nx][ny] > visited[x][y] + 1 :
                            visited[nx][ny] = visited[x][y] + 1
                            q.append((nx, ny))
                    elif array[nx][ny] == 0 :  # 벽이 없는 곳이면
                        if visited[nx][ny] > visited[x][y] :
                            visited[nx][ny] = visited[x][y]
                            q.append((nx, ny))
                # 아직 방문하기 이전이면
                elif visited[nx][ny] == -1 :
                    if array[nx][ny] == 1 : # 벽이 있는 곳이면
                        visited[nx][ny] = visited[x][y] + 1
                    elif array[nx][ny] == 0 : # 벽이 없는 곳이
                        visited[nx][ny] = visited[x][y]
                    q.append((nx, ny))

    return visited[-1][-1]



M, N = map(int, input().split()) # 가로, 세로
array = list(list(map(int, input().strip())) for _ in range(N))
print(solution(M, N, array))