[Baekjoon] 2206번 벽 부수고 이동하기

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제

Example 1:

Input: 
6 4
0100
1110
1000
0000
0111
0000
Output: 
15

Example 2:

Input:
4 4
0111
1111
1111
1110
Output:
-1

조건

시간 제한 : 2초

메모리 제한 : 192 MB

풀이과정

내 풀이

처음에는 여타 미로문제처럼 그리디하게 최소값을 갱신하는 식으로 풀이하였다. 하지만 해당 글을 보니 당장 이 지점까지 어떻게든 최단으로 오는 길만 구했다고 해서, 그 이후의 여정도 최적이라는 보장이 없다는 것을 깨달았고 벽을 0개 부쉈을 때, 벽을 1개 부쉈을 때로 나누어 계산해야 함을 깨달았다.

풀이 방식은 비슷하게 한거 같은데 python으로는 시간초과가 나와서 pypy3로 제출하였다. 코드에 좀 더 최적화가 필요한 모양이다.

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

# 무한대 정의
INF = int(1e9)

# n, m 입력받기
n, m = map(int, input().split())

# 그래프 입력받기
graph = []
for _ in range(n):
    graph.append(list(map(int,input().rstrip())))

# 이동 설정
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# bfs 실행
# 시작 위치 설정
x, y = 0, 0

q = deque()
# x y 좌표, 부순 벽 개수
q.append((x, y, 0))

#graph[x][y] = 1
ans = int(1e9)

# x / y / 벽 몇개 깨졌는지 / 경로
visited = [[[[False, 0] for _ in range(2)] for _ in range(m)] for _ in range(n)]
q = deque()

# bfs 실행
visited[0][0][0][0] = True
visited[0][0][0][1] = 1

q = deque()
q.append((0, 0))

while q:
    x, y = q.popleft()
    # 벽여부에 따라 2가지로 나누어 진행.
    for i in range(2):
        if visited[x][y][i][0] == False:
            continue
        visited[x][y][i][0] = True
        for j in range(4):
            nx = x + dx[j]
            ny = y + dy[j]
 
            # 벽이 2개이상이 되거나 맵을 벗어나면 취급하지 않는다.
            if nx <= -1 or ny <= -1 or nx >= n or ny >= m:
                continue
     
            if i + graph[nx][ny] > 1:
                continue

            if visited[nx][ny][i + graph[nx][ny]][0] == False and visited[nx][ny][i + graph[nx][ny]][1] == 0:
                q.append((nx, ny))
                visited[nx][ny][i + graph[nx][ny]][0] = True
                visited[nx][ny][i + graph[nx][ny]][1] = visited[x][y][i][1] + 1

# 답 출력
if visited[n-1][m-1][0][1] == 0 and visited[n-1][m-1][1][1] == 0:
    print(-1)
elif visited[n-1][m-1][0][1] != 0 and visited[n-1][m-1][1][1] == 0:
    print(visited[n-1][m-1][0][1])
elif visited[n-1][m-1][0][1] == 0 and visited[n-1][m-1][1][1] != 0:
    print(visited[n-1][m-1][1][1])
else:
    print(min(visited[n-1][m-1][0][1],visited[n-1][m-1][1][1]))

최적화한 코드

다른 풀이를 참고하여 최적화하였다. bfs 진행도중 정답이 나오면 끝낼 수 있도록 하였고 True, False를 0으로 대체하여 방문여부와 벽 세는걸 동시에 할 수 있게 하였다.

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

# n, m 입력받기
n, m = map(int, input().split())

# 그래프 입력받기
graph = []
for _ in range(n):
    graph.append(list(map(int,input().rstrip())))

# 이동 설정
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# bfs 실행
visited = [[[0, 0] for _ in range(m)] for _ in range(n)]
# 시작 위치 설정
x, y = 0, 0

q = deque()
# x y 좌표, 부순 벽 개수
q.append((x, y, 0))

q = deque()

# bfs 실행

def bfs():
    visited[0][0][0] = 1

    q = deque()
    q.append((0, 0))

    while q:
        x, y = q.popleft()

        if x == n-1 and y == m-1:
            ans = 0
            for i in range(2):
                if visited[x][y][i] != 0:
                    ans = visited[x][y][i]
            return ans

        # 벽여부에 따라 2가지로 나누어 진행.
        for i in range(2):
            if visited[x][y][i] == 0:
                continue

            for j in range(4):
                nx = x + dx[j]
                ny = y + dy[j]

                # 벽이 2개이상이 되거나 맵을 벗어나면 취급하지 않는다.
                if nx <= -1 or ny <= -1 or nx >= n or ny >= m:
                    continue

                if i + graph[nx][ny] > 1:
                    continue

                if visited[nx][ny][i + graph[nx][ny]] == 0:
                    q.append((nx, ny))
                    visited[nx][ny][i + graph[nx][ny]] = visited[x][y][i] + 1

    return -1

print(bfs())