많은 시행착오가 있었던 문제다.
가장 처음에 내가 생각한 방법은 "그냥 BFS 때리면서 벽을 지났는지 안지났는지 세고, 한번도 안지났으면 지나자" 였는데 틀렸다.
어디서 틀렸을까 고민해보다 나온 결론은 한번 벽을 뚫고 간 쪽에서 그 다음벽 주변을 먼저 탐색해버려서 벽을 한번도 안뚫으면 그 주변에 아예 접근도 못한다는 거였다.
그래서 생각한 다음 방법은 모든 벽을 기준으로 벽에서부터 BFS를 해서 시작점과 끝점까지 얼마나 걸리는지 측정하고, 그 합이 가장 작은값을 취하는 거였는데, 당연하게도 시간초과가 났다. 벽이 100개면 BFS를 100번, 1000개면 1000번 돌려야하니 당연한 결과...
마지막으로 생각한 방법은 0,0에서 BFS한번, 도착점에서 BFS 한번 하고 모든 벽의 4방향 주변을 체크하여 0,0에서 가장 빠른값과 도착점에서 가장 빠른값의 합의 최솟값을 구하는 방법이었다.
완벽한 풀이라고 생각했는데, 틀렸다...
그래서 왜 틀렸을까 질문게시판을 찾아봤는데 결론은 "벽이 한개도 없을 수도 있었다!"
벽이 한개도 없으면 -1을 출력하니 틀린 것이었다.
최종적인 코드는 이러하다.
import sys
input = sys.stdin.readline
from collections import deque
import copy
INF = 10**9
N,M = map(int,input().split())
dy = [1,-1,0,0]
dx = [0,0,1,-1]
Map1 = []
for i in range(N):
Map1.append(list(map(int,list(str(input().strip())))))
Map2 = copy.deepcopy(Map1)
def BFS(Y,X,Map):
dq = deque()
dq.append((Y,X,2))
while dq:
y,x,num = dq.popleft()
if Map[y][x] != 0:
continue
Map[y][x] = num
for i in range(4):
y1 = y+dy[i]
x1 = x+dx[i]
if y1>=0 and y1<N and x1>=0 and x1<M:
if Map[y1][x1] == 0:
dq.append((y1,x1,num+1))
lenlist = deque()
def checkwall(Y,X):
len1 = INF
len2 = INF
for i in range(4):
y1 = y+dy[i]
x1 = x+dx[i]
if y1>=0 and y1<N and x1>=0 and x1<M:
if Map1[y1][x1] > 1:
len1 = min(len1,Map1[y1][x1])
if Map2[y1][x1] > 1:
len2 = min(len2,Map2[y1][x1])
if len1 != INF and len2 != INF:
lenlist.append(len1+len2-1)
wall = deque()
for i in range(N):
for j in range(M):
if Map1[i][j] == 1:
wall.append((i,j))
BFS(0,0,Map1)
BFS(N-1,M-1,Map2)
for y,x in wall:
checkwall(y,x)
if lenlist:
print(min(lenlist))
else:
if Map1[N-1][M-1]>1:
print(Map1[N-1][M-1]-1)
else:
print(-1)Map을 deepcopy해서 두개로 나눈 다음 한번은 0,0에서, 한번은 도착점에서 BFS를 실행한다.
그리고 모든 벽의 좌표를 불러온 뒤, checkwall 함수를 실행하여 각 벽에서 0,0과 도착점까지의 거리의 최솟값의 합을 구한다. 그리고 마지막으로 벽이 아예 없는 경우도 있을 수 있으니, 벽에서 출발한 최솟값의 합이 없더라도 0,0에서 BFS했을때 도착점에 도달한 경우 그 값을 출력한다.
3000ms정도 나왔는데, 비효율적인가? 싶어서 다른 사람들 코드 보니까 python은 나보다 더 오래 걸린 사람들이 대부분이었다.
다른사람들 풀이를 보니 3차원 배열을 이용하는 방식이 많아보였다. 그 방법도 나중에 고려해봐야겠다.
오늘의 교훈) 항상 극단적인 반례를 염두하고 문제를 풀자