난이도

Gold 3

풀이 참고 유무

o

막힌 부분

시간 초과

문제

문제 바로가기
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을 출력한다.

예제 입력

6 4
0100
1110
1000
0000
0111
0000

예제 출력

15

문제 검토

BFS로 문제를 해결해야 하는데 먼저 떠오르는 것은 조합이다.

풀이(python)

Python - combinations(조합) 사용 - 시간 초과

from collections import deque
from itertools import combinations
row,col=map(int,input().split())
matrix=[list(map(int,input())) for _ in range(row)]
walls=[]
for x in range(row):
    for y in range(col):
        if matrix[x][y]==1:
            walls.append([x,y])                    
def BFS(ma):
    q=deque()
    q.append((0,0))
    ma[0][0]=1
    while q:
        r,c=q.popleft()
        dx=[-1,1,0,0]
        dy=[0,0,-1,1]
        for mv in range(4):
            nr=r+dx[mv]
            nc=c+dy[mv]
            if nr<0 or nr>=row or nc<0 or nc>=col:
                continue
            if ma[nr][nc]>0:
                continue
            ma[nr][nc]=ma[r][c]+1
            q.append((nr,nc))
    return ma[row-1][col-1]

min_distance=9999999        
for wall in combinations(walls,1):  
    for x in range(row):
        for y in range(col):                        
            matrix[x][y]=0
    for x in walls:        
        matrix[x[0]][x[1]]=1
    matrix[wall[0][0]][wall[0][1]]=0
    c=BFS(matrix)
    if c!=0:
        min_distance=min(c,min_distance)    
if min_distance==9999999:
    print(-1)
else:
    print(min_distance)

먼저 조합을 사용해서 풀어보았다.
벽의 좌표들을 다 모아서 그 중 1개를 선택했을 때 최단경로중 0이 아닌 가장 작은 것을 가져왔다.
테케는 다 맞았지만 itertools의 combination은 O(n!)의 수행시간을 갖는다고 한다.
O(n2)보다 훨씬 복잡도가 높은 시간이고 이 문제에서 벽의 개수는 n*m, 즉 1,000,000의 데이터 셋을 가질 수 있게되고 이것 O(n!)으로 돌렸다가는 어마 어마한 시간이 걸리게 되는 것이다.

Python - 2차 풀이 - 시간 초과

from collections import deque
row,col=map(int,input().split())
matrix=[list(map(int,input())) for _ in range(row)]
walls=[]
for x in range(row):
    for y in range(col):
        if matrix[x][y]==1:
            walls.append([x,y])                    
def BFS(breakwall,ma):
    q=deque()
    q.append((0,0))
    ma[0][0]=1
    while q:
        r,c=q.popleft()
        dx=[-1,1,0,0]
        dy=[0,0,-1,1]
        for mv in range(4):
            nr=r+dx[mv]
            nc=c+dy[mv]
            if nr<0 or nr>=row or nc<0 or nc>=col:
                continue
            if nr==breakwall[0] and nc==breakwall[1]:
                ma[nr][nc]=ma[r][c]+1
                q.append((nr,nc))
                continue            
            if ma[nr][nc]>0:
                continue
            ma[nr][nc]=ma[r][c]+1
            q.append((nr,nc))
    return ma[row-1][col-1]
min_distance=9999999    
for x in walls:
    matrixc=[mat[:] for mat in matrix]
    c=BFS(x,matrixc)
    if c!=0:
        min_distance=min(min_distance,c)        
if min_distance==9999999:
    print(-1)
else:
    print(min_distance)

combination의 수행 속도의 문제라고 생각했다.
하지만 생각해보니 combination에서도 n개중 1개만을 선택하는 것이기 때문에 위 코드와 수행시간에 차이는 별로 없었다.

위 코드도 1의 좌표들을 하니씩 보내면서 bfs를 돌리는 문제인데 당연히 똑같이 시간 초과가 날 수밖에 없었다.

그렇다면 결국 n*m의 시간을 걸리게 하는 1이 하나씩 없는 모든 경우의 수를 구하는 방식이 잘못됐다는 것인데 도무지 아이디어가 떠오르지 않아서 결국 풀이를 보고 이해한 뒤 다시 안보고 풀어보았다.

Python - 정석 풀이 - 3차원 행렬 사용(정답)

from collections import deque
row,col=map(int,input().split())
matrix=[list(map(int,input())) for _ in range(row)]
visited=[[[0 for _ in range(2)] for _ in range(col)] for _ in range(row)]

def bfs():
    q=deque()
    q.append([0,0,0])
    visited[0][0][0]=1
    while q:
        r,c,crush=q.popleft()
        dx=[-1,1,0,0]
        dy=[0,0,-1,1]
        if r==row-1 and c==col-1:
            print(visited[r][c][crush])
        for mv in range(4):
            nr=r+dx[mv]
            nc=c+dy[mv]            
            if nr<0 or nr>=row or nc<0 or nc>=col:
                continue
            #벽이 뚫린 세계가 아니고 만약 벽을 만났다면
            if matrix[nr][nc]==1 and crush==0:
                #벽이 뚫린 세계로 이동
                visited[nr][nc][1]=visited[r][c][0]+1
                q.append([nr,nc,1])
            #어떤 세계이든 한번도 방문하지 않은 곳이고 벽이 아니라면
            elif matrix[nr][nc]==0 and visited[nr][nc][crush]==0:
                #방문처리
                visited[nr][nc][crush]=visited[r][c][crush]+1
                q.append([nr,nc,crush])
    return -1
print(bfs())

결국 방법은 '벽이 하나가 뚫린 차원'과 '벽이 뚫리지 않은 차원' 이 두개의 매트릭스를 3차원행렬로 표현하여 문제를 푸는 방법이다.

벽이 하나 뚫린 세계에서 벽은 딱 한번만 뚫릴 수 있다.
최단 경로중의 최단 경로를 찾는 것이다.
벽이 하나 뚫린 세계에서 맨 끝점에 도달하게 되는 경로는 뚫린 경로 중 가장 최단 경로 일 것이다.

#아이디어
매트릭스 2개 ( 벽이 한번도 안 뚫린 세계), (벽이 한번 뚫린 세계)를 준비한다.
똑같이 BFS를 진행하되 벽이 한번도 안뚫렸는데 벽을 만나면 경로로 인정한다.
그 후 벽이 한번 뚫린 세계에서 경로를 계산한다.

#시간복잡도
BFS는 한번만 수행할 것이므로 O(v*e)를 구한다.
v는 1000x1000x2으로 최대 200만개 e는 간선을 최대 4개 갖고있다고 할 수 있으므로 4x200만 결국 연산 횟수는 200만 + 800만 = 1000만이라고 보고 이는 1초 연산 횟수인 1억~2억에 못 미친다는 것을 알 수 있다.
이전 풀이에서 100만 x 100만의 연산 횟수를 사용해서 시간 초과가 났기 때문에 이 풀이가 매우 정석적인 풀이라고 할 수 있다.

#자료구조
int[n][m][2]:방문확인 , int[n][m][2] : 2차원 matrix 2개, queue=bfs

걸린 시간

28:16 (조합 풀이 - 시간 초과)
x

총평

이런 유형의 문제가 있을 때 차원을 하나 더 생성하는 것도 잘 생각해봐야한다.
어떠한 조건이 어떤 경로에도 똑같이 적용 된다면 그 조건을 통과한 matrix를 하나 더 만드는 것이다.