2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
import sys
from collections import deque
sys.setrecursionlimit(10000)
if __name__ == '__main__':
N, M = map(int, sys.stdin.readline().rstrip('\n').split())
graph = []
wall_points = []
for i in range(N):
l = list(sys.stdin.readline().rstrip('\n'))
graph.append(l)
def bfs(v):
queue = deque([(0, 0, 0)])
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
pos = queue.popleft()
cur_v = pos[0]
cur_h = pos[1]
z = pos[2]
for d in direction:
nn, nm = cur_v + d[0], cur_h + d[1]
if nn < 0 or nn >= N or nm < 0 or nm >= M:
continue
if graph[nn][nm] == '0' and v[nn][nm][z] == 0:
v[nn][nm][z] = v[cur_v][cur_h][z] + 1
queue.append((nn, nm, z))
# 깨진적이 없는 벽을 만났을때
elif z == 0 and graph[nn][nm] == '1' and v[nn][nm][1] == 0:
v[nn][nm][1] = v[cur_v][cur_h][0] + 1
queue.append((nn, nm, 1))
visited = [[[0] * 2 for i in range(M)] for i in range(N)]
if N == 1 and M == 1:
print(1)
else:
bfs(visited)
ans1 = visited[N-1][M-1][0]
ans2 = visited[N - 1][M - 1][1]
if ans1 == 0 and ans2 == 0:
print(-1)
else:
if ans1 == 0 or ans2 == 0:
print(max(ans1, ans2) + 1)
else:
print(min(ans1, ans2) + 1)
아.. 최근 며칠간 DFS, BFS 문제를 풀었는데 너무 쉽다고 자만하고 있다가 이 문제를 만나고 큰코 다쳤다.
처음에는 연구소 문제처럼 벽을 뚫는 모든 경우를 확인하면 되겠구나하고 후다닥 풀었는데 왠걸.. 바로 시간초과가 났다.
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
이 문제는 연구소처럼 모든 경우에 대해 DFS 혹은 BFS를 수행할 필요 없이 단 한번의 수행으로 풀어야한다.
나도 오래 고민하다가 결국 다른분의 풀이를 확인하고 나서도 많이 헷갈렸다.
핵심아이디어는 아래와 같다.
1. 방문 처리하는 방문 기록 배열을 N*M*2 크기의 3차원 배열로 만든다
일반적인 DFS/BFS는 하나의 케이스에 대해서만 방문처리를 하면 되기때문에 문제로 주어지는 그래프(맵)와 동일한 크기의 배열을 생성한후, 방문 처리를 하면 되지만
이 문제의 경우 벽을 뚫은 경우에 대한 방문기록과 벽을 뚫지 않은 경우에 대한 방문기록을 별도로 해야하기 때문에 마지막 차원을 2의 크기로 갖는 3차원 배열을 만드는 것이다.
2. BFS를 수행할때 현재 큐에서 꺼낸값이 벽을 뚫지 않은 경우 즉, 소스상에서 z가 0 인 경우이고 벽에 도달했다면 해당 벽으로 이동(벽을 부숨)하고 발자국을 기록한다. (소스상 bfs 함수내 else 부분이다) 벽을 부쉈으므로 방문처리 배열의 3차원의 2번째 인덱스에 기록을 해줘야한다.
3. 나머지는 일반 bfs 와 동일하게 진행하면 벽을 부순 케이스는 방문배열 3차원의 2번째 벽을 부수지 않은 케이스는 1번째 배열로 진행된다.
어렵고 신선한 문제였다. Good
아래는 처음 연구소문제처럼 풀어서 시간초과가 발생한 소스.
import sys
from collections import deque
sys.setrecursionlimit(10000)
if __name__ == '__main__':
N, M = map(int, sys.stdin.readline().rstrip('\n').split())
graph = []
wall_points = []
for i in range(N):
l = list(sys.stdin.readline().rstrip('\n'))
graph.append(l)
for j in range(len(l)):
if l[j] == '1':
wall_points.append((i, j))
def bfs(cur_n, cur_m, f):
queue = deque([(cur_n, cur_m)])
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
pos = queue.popleft()
if pos[0] == N - 1 and pos[1] == M - 1:
return f[pos[0]][pos[1]] + 1
for d in direction:
nn, nm = pos[0] + d[0], pos[1] + d[1]
if nn < 0 or nn >= N or nm < 0 or nm >= M:
continue
if graph[nn][nm] == '0' and f[nn][nm] == 0:
f[nn][nm] = f[pos[0]][pos[1]] + 1
queue.append((nn, nm))
return -1
ans = -2
for i in range(len(wall_points)):
nn, nm = wall_points[i]
# 벽 부수기
graph[nn][nm] = '0'
foots = [[0] * M for _ in range(N)]
ans = max(ans, bfs(0, 0, foots))
# 벽 원상태로 돌려놓기
graph[nn][nm] = '1'
print(ans)