[골드 4] 1261번: 알고스팟

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

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)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

---

사고의 흐름

• (1, 1)에서 BFS를 돌리기 시작해서 다음 칸이 1이면 List에 이전 Count보다 1을 늘려 저장하고, 다음 칸이 0이면 이전 Count를 그대로 저장하면 되겠네. 만약 List에 값이 저장되어 있으면, 그냥 예외 처리하지 말고 저장된 값과 현재 Count(또는 Count + 1)의 크기를 비교해서 더 작은 값을 저장하면 되겠다.
• 일단 이렇게 풀고 시간 초과 뜨면 다시 생각해보자. 더 최적화할 여지가 있기는 해 보인다.

 

• 시간 초과는 안 뜨는데 틀렸습니다가 뜬다. 극단적인 Test Case에서 틀렸나?
• (M, N) = (1, 1) 로 설정하고 돌려봐도 정상적으로 작동한다. 그렇다면 Logic에 문제가 있다는 뜻인데.
• bfs() 함수를 현재 순회하는 좌표가 끝 지점인 (M-1, N-1) 에 도달하면 Return하도록 설정했는데, 문제는 현재 좌표가 끝에 도달하자마자 Return하면 다른 더 좋은 경로를 고려할 수가 없다. 그래서 틀렸나보다.
• 그럼 Queue를 전부 다 비운 뒤에 Return하도록 함수를 수정해야겠다.

내가 작성한 소스코드

import sys
from collections import deque

r = sys.stdin.readline


def bfs(maze, cnt_breaks, end):
    q = deque()
    q.append((0, 0))
    cnt_breaks[0][0] = 0
    end_y = end[0]; end_x = end[1]

    while q:
        (y, x) = q.popleft()
            
        for (ny, nx) in ((y, x+1), (y+1, x), (y, x-1), (y-1, x)):
            if (0 <= ny and ny <= end_y) and (0 <= nx and nx <= end_x):
                if maze[ny][nx] == 0:
                    if cnt_breaks[ny][nx] == -1 or cnt_breaks[ny][nx] > cnt_breaks[y][x]:
                        cnt_breaks[ny][nx] = cnt_breaks[y][x]
                        q.append((ny, nx))
                elif maze[ny][nx] == 1:
                    if cnt_breaks[ny][nx] == -1 or cnt_breaks[ny][nx] > cnt_breaks[y][x] + 1:
                        cnt_breaks[ny][nx] = cnt_breaks[y][x] + 1
                        q.append((ny, nx))

    print(cnt_breaks[end_y][end_x])
    return
    

m, n = map(int, r().split())
maze = [[] for _ in range(n)]
for i in range(n):
    maze[i] = list(map(int, r().rstrip()))
cnt_breaks = [[-1] * m for _ in range(n)]

bfs(maze, cnt_breaks, (n-1, m-1))

남이 작성한 소스코드

chay116 님:
https://www.acmicpc.net/source/18966674

피드백

• Queue를 두 개 써서 첫 번째 Queue는 벽이 0인 경우, 두 번째 Queue는 벽이 1인 경우를 따로 저장하면 훨씬 빠르게 탐색을 수행할 수 있다. 먼저 첫 번째 Queue의 원소를 모두 탐색한 뒤, 두 번째 Queue를 첫 번째 Queue에 복사한다. 그런 다음 다시 첫 번째 Queue를 모두 탐색하는 과정을 반복하면 최소한의 벽을 뚫어서 가는 경로를 빠르게 찾을 수 있다.
• 간선 간의 비용이 다르므로 다익스트라 알고리즘을 쓰면 더 쉽게 풀 수 있다. 나중에 배운 뒤에 다시 풀어보자.
• Tuple을 함수에 넘겨줄 때는 매개변수를 def foo(a, b): 형식으로 작성하면 안된다. def foo(Tuple): 처럼 작성한 다음 함수 내에서 a = Tuple[0]; b = Tuple[1] 로 할당해 사용해야 한다.