[Python 3] BOJ - 1261 "알고스팟"

 # 문제 링크 : https://www.acmicpc.net/problem/1261

1261번: 알고스팟

 # 풀이 :

개인적으로 문제의 핵심은 벽인 경우와 뚫려있는 경우를 큐에 다르게 넣는 것이라 생각한다. 문제에서 벽을 부수는 횟수의 제한은 없지만 벽을 부수는 횟수를 최소화하라고 하였기 때문이다. bfs는 큐의 가장 먼저 들어온 원소를 뽑기 때문에 벽과 벽이 아닌 칸을 같은 우선순위로 취급하게 되면 최소값을 구할 수 없다.

<그림 1. 6 x 6 미로>

 설명 상 편의를 위해 4방향을 동쪽, 남쪽, 서쪽, 북쪽 순으로 돈다고 가정한다. 따라서 현재 큐에 들어가는 지점은 빨간색으로 처리하였고, 그 중에서도 동쪽인 0행 1열 먼저 큐에 들어가고 남쪽인 1행 0열이 큐에 순차적으로 들어가게 된다. 또한 현재 정점은 초록색으로 나타내었다. 큐에 넣을 때는 (x좌표, y좌표, 이 때까지 부순 벽의 횟수)로 넣는다.

<그림 2. 그림 1 이후 단계>

 현재 정점이 0행 1열로 바뀌었고 이미 방문한 정점과 범위를 벗어나는 정점을 제외하고 갈 수 있는 정점은 (1, 0)과 (1, 1)인데 모두 벽이므로 큐에 (1, 0, 1)과 (1, 1, 1)을 넣는다

<그림 3. 그림 2 이후 단계>

 현재 정점이 1행 0열로 바뀌었다. 1행 0열로 올 때 까지 벽을 한번도 부수지 않았으므로 이후 큐에 삽입될 2행 0열은 (2, 0, 0)의 형태로 들어가게 된다.

<그림 4. 그림 3 이후의 단계>

 현재 정점이 0행 2열로 바뀌었고, 현재 정점에 오기까지 벽을 하나 부쉈는데, 동쪽으로 인접한 0행 3열 역시 벽이므로 0행 3열로 가려면 벽을 한 번 더 부숴야 한다. 따라서 큐에는 (0, 3, 2)를 넣고, 남쪽으로 인접한 1행 2열은 벽은 아니지만 현재 정점이 이미 한번 벽을 부쉈기 때문에 (1, 2, 1)을 큐에 넣어야 한다.

<그림 5. 그림 4 이후의 단계>

 현재 정점이 1행 1열로 바뀌었다. 문제는 여기서 시작한다. 현재 동남서북의 방향 중 방문하지 않은 정점은 2행 1열밖에 없다. 또한 2행 1열은 벽은 아니지만 현재 정점으로 올 때 이미 벽을 한번 부쉈으므로 큐에 넣을 때 (2, 1, 1)의 형태로 넣어야 한다. 그런데, 2행 1열로 가는 경로 중 벽을 한번도 부수지 않고도 갈 수 있는 경로가 존재한다. 0행 0열 -> 1행 0열 -> 2행 0열 -> 2행 1열 순으로 간다면 벽을 한번도 부수지 않고도 갈 수 있다. 즉, 벽인 곳과 벽이 아닌 곳을 같은 우선순위로, 즉 그냥 일괄적으로 맨 뒤에 쌓는다면 같은 장소에 대해 벽을 최소로 부수는 횟수를 정확히 구할 수 없다. 따라서, 벽은 맨 끝에 넣어 큐에서 벽이 아닌 곳을 다 소진했을 때 대안적으로 꺼내야 한다. 반대로 벽이 아닌 곳은 맨 처음에 넣어야 벽인 곳이 뒤쪽으로 밀리면서 최대한 벽을 늦게 부술 수 있다. 

 

 # 코드

import sys, collections

# dx : x의 이동방향
# dy : y의 이동방향
dx = [0,0,1,-1]
dy = [1,-1,0,0]

# 입력부
m,n = map(int, sys.stdin.readline().split())
maze = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

# check : x행 y열을 방문했는지 조사하는 2차원 배열
check = [[False] * m for _ in range(n)]
q = collections.deque()

# 0행 0열 처리
q.append((0,0,0))
check[0][0] = True

ans = 9876542310
while q:
    x,y,z = q.popleft()
    # 현재 정점이 도착 정점이면 최소값 갱신
    if x == n - 1 and y == m - 1:
        ans = min(ans, z)
        continue
    for i in range(4):
        nx,ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if check[nx][ny] == False:
                check[nx][ny] = True
                # 범위안에 있고 아직 방문하지 않은 경우
       
                if maze[nx][ny] == '1':
                    # 만일 다음 장소가 벽이라면 부순 횟수 1증가 후 큐의 마지막에 삽입
                    nz = z + 1
                    q.append((nx,ny,nz))
                else:
                    # 만일 다음 장소가 벽이 아니라면 그대로 큐의 처음에 삽입
                    nz = z
                    q.appendleft((nx,ny,nz))

# 정답 출력
print(ans)