[BOJ] 2206 벽 부수고 이동하기 (Python3)
문제
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을 출력한다.
예제
1
2
3
4
5
6
7
8
9
10
11
예제 입력 1
6 4
0100
1110
1000
0000
0111
0000
예제 출력 1
15
1
2
3
4
5
6
7
8
9
예제 입력 2
4 4
0111
1111
1111
1110
예제 출력 2
-1
문제 풀이
맨 처음에는 맵을 돌면서 1인경우에는 벽을 깼다고 가정하고 잠깐 1을 0으로 바꾼뒤 dfs를 한번 돌리고, 끝까지 도달하면 result에 최단거리를 넣어주고 아니면 넣지않는 식으로 모든 1에 대한 벽을 깬 경우를 구했다. 이렇게 하니까 답은 같게 나왔지만, dfs를 모든 좌표마다 한번씩 실행하므로 시간초과가 떴다.
틀린 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from collections import deque
n,m = map(int,input().split())
count = 0
dx = [1,-1,0,0]
dy = [0,0,1,-1]
q = deque()
def dfs(graph):
visited = [[0 for _ in range(m)]for _ in range(n)]
q.append([0,0])
visited[0][0] += 1
while q:
x,y = q.popleft()
for i in range(4):
sx = x+dx[i]
sy = y+dy[i]
if 0 <= sx < n and 0<= sy < m and graph[sx][sy] == 0 and visited[sx][sy]== 0:
q.append([sx, sy])
visited[sx][sy]= visited[x][y]+1
if visited[n-1][m-1] == 0:
return -1
else:
return visited[n-1][m-1]
graph = []
for i in range(n):
graph.append(list(map(int, input())))
result = []
for i in range(n):
for j in range(m):
if graph[i][j] == 1:
graph[i][j] = 0
answer = dfs(graph)
if answer == -1:
graph[i][j] = 1
continue
else:
result.append(answer)
graph[i][j] = 1
else:
answer = dfs(graph)
if answer == -1:
continue
else:
result.append(answer)
if result:
print(min(result))
else:
print(-1)
1
2
3
4
5
6
7
8
6 4
0100
1110
1000
0000
0111
0000
15
그래서 해답을 검색해서 보니, 3차원 배열을 사용하는 문제였다. 사실 해답을 보고도 3차원 배열로 하려니까 헷갈려서 생각을 하느라 어려웠는데, 역시 말로 보는것 보다 직접 코딩한번 해보는게 훨씬 이해가 빨랐다.
3차원 배열의 visited를 생성해준다. 원래 visited는 nm의 크기의 0이나 False를 갖는 이차원 배열이지만, 이번에는 nm 크기의 [0,0]을 갖는 3차원 배열이다. 원래의 dfs처럼 [0]의 인덱스의 값에 경로의 값만큼을 세주다가, 벽을 만나면 그 벽을 부쉈다고 가정하고 [1]의 인덱스에 경로를 저장하기 시작한다. 그럼 [0]의 인덱스는 벽을 부수지 않았을때의 최단경로이고, [1]의 인덱스는 벽을 부수고 갔을때의 최단경로가 된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from collections import deque
def dfs():
q.append([0,0,0])
visited[0][0][0] = 1
while q:
x,y,z = q.popleft()
if x == n-1 and y == m-1:
return visited[x][y][z]
for i in range(4):
sx = x+dx[i]
sy = y+dy[i]
if 0 <= sx < n and 0<= sy < m:
if graph[sx][sy] == 1 and z == 0:
visited[sx][sy][1] = visited[x][y][0]+1
q.append([sx,sy,1])
elif graph[sx][sy] == 0 and visited[sx][sy][z] == 0:
visited[sx][sy][z] = visited[x][y][z]+1
q.append([sx,sy,z])
return -1
n,m = map(int,input().split())
count = 0
dx = [1,-1,0,0]
dy = [0,0,1,-1]
q = deque()
visited = [[[0]*2 for _ in range(m)]for _ in range(n)]
graph = []
for i in range(n):
graph.append(list(map(int, input())))
print(dfs())
answer1 = visited[n-1][m-1][0]
answer2 = visited[n-1][m-1][1]
1
2
3
4
5
6
7
8
6 4
0100
1110
1000
0000
0111
0000
15
댓글남기기