[Python] 백준 1261번 - 알고스팟 (골드 4)

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 그래프
 - 다익스트라
 - 최단 경로
 - 0-1 BFS

 

https://www.acmicpc.net/problem/1261

 

문제

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

 

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

---

 

처음엔 단순한 bfs문제로 풀었다.

 

하지만 시간초과가 발생했고 PyPy3로 제출 시 메모리 초과가 발생했다.

 

그래서 0-1BFS 알고리즘에 대해서 검색해 보니 데큐를 이용하여 우선순위를 임의로 지정하여 마치 우선순위큐처럼 활용하는 방법이 있었다.

 

n, m = map(int, input().split())
maze = [ [0 for _ in range(n)] for _ in range(m)]
for i in range(m):
    s = input().rstrip()
    for j in range(n):
        maze[i][j] = int(s[j])

from collections import deque
q = deque()

visited = [ [-1 for _ in range(n)] for _ in range(m)]

q.append((0, 0))
visited[0][0] = 0

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

while q:
    x, y = q.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 maze[nx][ny] == 1: # 벽이면 부수고 +1
                    visited[nx][ny] = visited[x][y]+1
                    q.append((nx, ny)) # 뒤로 넣기
                else: # 벽이 아니면 그대로
                    visited[nx][ny] = visited[x][y]
                    q.appendleft((nx, ny)) # 앞으로 넣기
            '''
            else: # 방문한 적이 있는데 기존 값이 더 작다면
                if visited[nx][ny] > visited[x][y]:
                    if maze[nx][ny] == 1:
                        visited[nx][ny] = visited[x][y]+1
                        q.append((nx, ny))
                    else:
                        visited[nx][ny] = visited[x][y]
                        q.appendleft((nx, ny))
            '''   
            if nx == m-1 and ny == n-1: # 목적지에 도달하면
                visited[nx][ny] = visited[x][y]
                q = deque() # 반복문 탈출
                break
                
print(visited[m-1][n-1])

 

처음엔 단순히 q.append()만 사용했다.

 

이후 0-1 BFS알고리즘을 알고난 뒤에 벽이 아닐 경우 appendleft()로 우선순위를 높여주고

벽일 경우에는 append()로 맨뒤로 보내주어 우선순위를 낮춰주었다.

 

그럼에도 불구하여 방문한 적이 있는 곳을 전체 주석처리 후 다시 제출하니 통과되었다.

 

생각해 보니 (0, 0)부터 (n, m) 방향으로 순차적으로 진행하는 문제이기 때문에 이미 방문한 적이 있다면 그곳의 숫자가 가장 빠른 값일 것이다.