당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 최단경로를 구하시오.
# 틀린 코드
처음엔 이전에 미로문제를 풀어봤기 때문에 단순한 BFS문제라고 생각했다. 생각보다 어렵네...
당연하지만 벽을 부순다는 조건을 해결하기 까다로웠다.
한번밖에 못뚫기 때문에 flag를 두고 뚫은 다음 그 주변을 queue에 넣어 bfs를 진행하는 방식으로 코드를 짰었다.
예제는 돌아가지만 6%에서 틀렸다. 틀린 이유는 뭐 예제보다 복잡한 상황일 때 최적의 답을 찾지못해서일 것이다.
코드에도 나왔듯이 원래 값과 대입할 값을 비교하여 최솟값을 넣는 코드가 있다. 근데 이게 유효할려면 정상적으로 한번 다 돌고 벽을 뚫는 방식으로 다시 돌아야 한다.
그럼 조건식이 달라지는데? 한번 더 돌 땐 정상적인 길이 0이 아니게 되는데?
그럼 차라리 그럼 graph 자체를 바꾸지말고 따로 저장을 할까?
벽을 뚫었을 때랑 안뚫었을 때를 비교하면 되는거 아냐?!?
import sys
from collections import deque
input = sys.stdin.readline
def bfs(x, y):
queue = deque([[x, y]])
flag = 1
mx = [-1, 1, 0, 0]
my = [0, 0, -1, 1]
while queue:
x, y = queue.popleft()
for i in range(4):
dx = x + mx[i]
dy = y + my[i]
if dx < 0 or dy < 0 or dx >= N or dy >= M:
continue
elif graph[dx][dy] == 0:
graph[dx][dy] = graph[x][y] + 1
if graph[dx][dy] and graph[dx][dy] != 1:
graph[dx][dy] = min(graph[dx][dy], graph[x][y] + 1)
queue.append([dx, dy])
if not queue and flag == 1: # 벽 한번 뚫기
for i in range(4):
dx = x + mx[i]
dy = y + my[i]
if dx < 0 or dy < 0 or dx >= N or dy >= M:
continue
graph[dx][dy] = graph[x][y] + 1
queue.append([dx, dy])
flag = 0
N, M = map(int, input().split())
graph = []
for _ in range(N):
graph.append(list(map(int, input().strip())))
bfs(0, 0)
if graph[N-1][M-1]:
print(graph[N-1][M-1]+1)
else:
print(-1)# 정답 코드
벽을 뚫었을 때와 안뚫었을 때를 비교하기 위해 3차원 배열을 이용하였다.
3번째 인자 w로 벽 격파 여부를 판단하여 w가 1일 때 벽을 뚫을 수 있고, 0일 땐 벽을 뚫을 수 없게 하였다.
벽을 뚫은 경우 3번째 인자 w를 0으로 두어 그 다음 벽을 뚫지 못하게 하고, 그 외에 벽이 없고 안가본 일반적인 경우에 대해 조건문을 처리하였다.
같은 미로문제라도 단순한 조건 하나로 문제난이도를 움직일 수 있는 것 같다.
- 좌표에 대한 추가 정보가 필요할 때 3차원 배열을 적극적으로 사용할 것 !
- 여러가지 경우 중 최소를 구할 경우 graph값을 직접 바꾸지 말 것 !
import sys
from collections import deque
input = sys.stdin.readline
def bfs():
queue = deque([[0, 0, 1]])
visited = [[[0]*2 for i in range(M)] for j in range(N)]
visited[0][0][1] = 1
while queue:
x, y, w = queue.popleft() # w == 1 일 때 벽을 뚫을 수 있음
if x == N-1 and y == M-1:
return visited[x][y][w]
mx = [-1, 1, 0, 0]
my = [0, 0, -1, 1]
for i in range(4):
dx = x + mx[i]
dy = y + my[i]
if dx < 0 or dy < 0 or dx >= N or dy >= M:
continue
if graph[dx][dy] == 1 and w == 1: # 벽이 있고 뚫을 수 있을 때
visited[dx][dy][0] = visited[x][y][1] + 1
queue.append([dx, dy, 0])
elif graph[dx][dy] == 0 and visited[dx][dy][w] == 0: # 벽이 없고 안가본 경우
visited[dx][dy][w] = visited[x][y][w] + 1
queue.append([dx, dy, w])
return -1
N, M = map(int, input().split())
graph = []
for _ in range(N):
graph.append(list(map(int, input().strip())))
print(bfs())