[BOJ] 벽 부수고 이동하기 (no.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을 출력한다.

쪼오금 매웠다...

🤔 생각

• 벽 부수는 경우만 해결하면 일반적인 bfs 문제와 같겠군.

• 어떤 벽을 부수냐에 따라 또 최단경로가 달라진다... 심지어 안 부순게 빠른 경우도 있다.

• 모든 벽을 한번씩 파라미터로 두고 bfs를 돌려봐야하나? 답이야 나오겠지만 세월아 네월아 끝에 나오는 답은 의미가 없다.

• 벽을 부수는 경우의 경로도 그래프를 구성하는 하나의 가지로 만들면 어떨까.

• 그렇다면, 벽을 만날 때마다 일단 부수고 큐잉해주고, 벽을 이미 한번 부쉈다는 사실을 계속 기억해나가게만 해주면 되는거 아닌가..? (브랜치가 하나 더 생기는 개념)

• 그럼 모든 벽이 전부 한번씩 큐잉 될 것이고

• 안 부순 경우도 자동으로 고려되고, bfs니까 먼저 도달한 놈이 무조건 최단경로일 것이고... 어 그렇네 되나? 이거 될거 같은데???

해서 아래 풀이로 3트 정도 끝에 솔브했다.

📌 내 풀이

import sys
input = sys.stdin.readline
print = sys.stdout.write

def main():
    n, m = map(int, input().split())
    grid = tuple(tuple(map(int, input().rstrip())) for _ in range(n))
    dx, dy = [1,-1,0,0], [0,0,1,-1]

    def bfs():
        visited = [[[False]*m for _ in range(n)] for _ in range(2)]
        q = [(0,0,False)]
        visited[0][0][0] = True
        dist = 1

        while q:
            tmp = []
            for x,y,broken in q:
                if x == n-1 and y == m-1: return dist
                
                for i in range(4):
                    nx, ny = x+dx[i], y+dy[i]

                    if 0 <= nx <n and 0 <= ny <m:
                        if grid[nx][ny] == 1 and not broken:
                            visited[0][nx][ny] = True
                            tmp.append((nx,ny,True))
                        elif grid[nx][ny] == 0 and not visited[broken][nx][ny]:
                            visited[broken][nx][ny] = True
                            tmp.append((nx,ny,broken))
            
            q = tmp
            dist += 1
        return -1

    print("%d" % bfs())

if __name__ == "__main__":
    sys.exit(main())

• 풀긴 했지만 메모리를 너무 많이 먹는 감이 있어서...

• 약간의 그리디를 반영해보았다. (벽을 안 부순 경우가 먼저 방문하면, 부순 경우는 큐잉하지 않음)

• 방문 리스트도 단순히 방문만을 표시하려다 보니 뚱뚱해지는거다. 방문 true/false가 아닌 벽을 부쉈는지, 안 부쉈는지 여부를 value로 저장하게 함으로써 리스트 차원을 줄여보자. (물론 초기화 상태는 별개 value로 구분해줘야 방문 여부 판단이 가능하다. )

주의
위와 같은 그리디는 우선순위가 명확한 상황에서만 적용해야한다.

그래서 개선한 풀이는 아래와 같다.

📌 최종의 최종 풀이

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    grid = tuple(input().rstrip() for _ in range(n))
    dx, dy = [1,-1,0,0], [0,0,1,-1]

    def bfs():
        cache = [[2]*m for _ in range(n)] # 0-벽안뚫음, 1-벽뚫음, 2-초기화(미방문 상태)
        q = [(0,0,0)]
        cache[0][0] = 0
        dist = 1

        while q:
            tmp = []
            for x,y,chance in q:

                if x == n-1 and y == m-1: return dist
                for i in range(4):
                    nx, ny = x+dx[i], y+dy[i]

                    if 0 <= nx <n and 0 <= ny <m:
                        if cache[nx][ny] > chance:
                            if grid[nx][ny] == '1' and chance != 1:
                                cache[nx][ny] = 1
                                tmp.append((nx,ny,1))
                            elif grid[nx][ny] == '0':
                                cache[nx][ny] = chance
                                tmp.append((nx,ny,chance))
            
            q = tmp
            dist += 1
        return -1

    print(bfs())

if __name__ == "__main__":
    sys.exit(main())

✔ 회고

• 그래프의 노드에 맵 정보만 포함될 수 있다는 편견을 버리자! 특수한 조건에 따라 브랜칭 할 수도 있다.