문제 링크
문제 설명
N*M 크기의 맵에서 0은 이동가능, 1은 이동 불가능한 벽을 나타낸다. (1,1)->(N,M)의 위치까지 이동할때의 최단경로는(처음+끝칸도 포함)?
- 이동하면서 1개의 벽을 부셨을때의 이동거리가 더 짧으면 부시기 가능
- 이동이 불가능하면 -1을 출력한다.
문제 풀이
시도 1
최단거리를 구하는 문제이므로 bfs로 풀려고 했다
1. N,M과 맵을 입력받는다.
: 맵을 입력받으면서 벽의 좌표를 따로 리스트에 저장한다.
2. 벽을 부시지 않은 경우 + 리스트속 벽 하나씩 부신 경우 bfs로 최단거리를 구한다
import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
map_pos = []
walls = []
N, M = map(int, input().split())
for i in range(N):
tmp = list(map(int, input().strip()))
for j in range(M):
if tmp[j] == 1:
walls.append((i,j))
map_pos.append(tmp)
def in_bound(x,y): #이동하려는 위치가 범위 안인지 검사
if x in range(0, N) and y in range(0, M):
return True
else:
return False
def bfs(map_pos):
visited = [[0]*M for _ in range(N)]
queue = deque([[(0,0),1]])
while queue:
(x,y),count = queue.popleft()
visited[x][y] = 1 #방문함을 표시
if x==N-1 and y==M-1: #끝까지 도착했을때
return count
for i in range(4): #상하좌우로 이동하기
if in_bound(x+dx[i], y+dy[i]):
if map_pos[x+dx[i]][y+dy[i]] == 0:
if visited[x+dx[i]][y+dy[i]] != 1:
queue.append([(x+dx[i], y+dy[i]), count+1])
return N*M+1 #모든 칸을 지나는 경우보다 클수는 없으므로 이렇게 설정
#벽을 부시지 않은 경우
answer = bfs(map_pos)
for x,y in walls:
#벽부시기
map_pos[x][y] = 0
count = bfs(map_pos)
answer = min(answer, count)
map_pos[x][y] = 1
if answer == N*M+1:
print(-1)
else:
print(answer)
hmmmmmmm...........😭
시도 2
N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)
-> map의 크기가 1000x1000이고 모든 칸이 1인 경우는 (NxM)^2번의 연산을 해야함!!! 그래서 시간초과가 났다
각 칸을 부시는 경우에 매번 bfs를 돌기가 아닌
-> 해당 칸까지 오는 경로에서 벽을 부셨는지 안부셨는지 판단하는 플래그를 visited 배열에 추가한다
import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
map_pos = []
walls = []
N, M = map(int, input().split())
for i in range(N):
map_pos.append(list(map(int, input().strip())))
def in_bound(x,y):
if x in range(0, N) and y in range(0, M):
return True
else:
return False
def bfs(map_pos):
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
#(x,y), count, 벽 부셨는지?
queue = deque([[(0,0),1,0]])
while queue:
(x,y),count,flag = queue.popleft()
visited[x][y][flag] = 1
for i in range(4):
if in_bound(x+dx[i], y+dy[i]):
if x+dx[i]==N-1 and y+dy[i] == M-1:
return count+1
#빈칸일때
if map_pos[x+dx[i]][y+dy[i]] == 0:
if visited[x+dx[i]][y+dy[i]][flag] != 1 and [(x+dx[i], y+dy[i]), count+1, flag] not in queue:
queue.append([(x+dx[i], y+dy[i]), count+1, flag])
#벽일때
else:
#벽 부시지 않음
if flag == 0 and visited[x+dx[i]][y+dy[i]][flag] != 1:
queue.append([(x+dx[i], y+dy[i]), count+1, 1])
return -1
print(bfs(map_pos))
진짜 맘같지 x,,
시도 3
- 해당 좌표의 visited를 pop했을때가 아닌 Push했을때 체크하는걸로 바꿈
- 매번 x+dx[i]를 계산하지 않고 nx 변수에 할당
- queue에 count까지 넣지 않고 visited에 아예 해당 좌표까지의 count를 담음
import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
map_pos = []
N, M = map(int, input().split())
for _ in range(N):
map_pos.append(list(map(int, input().strip())))
def in_bound(x,y):
if x in range(0, N) and y in range(0, M):
return True
else:
return False
def bfs(map_pos):
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
#(x,y), 벽 부셨는지?
queue = deque([[(0,0),0]])
visited[0][0][0] = 1
while queue:
(x,y),flag = queue.popleft()
if x == N-1 and y == M-1:
return visited[x][y][flag]
for i in range(4):
nx = x+dx[i]
ny = y+dy[i]
if in_bound(nx, ny):
#빈칸일때
if map_pos[nx][ny] == 0 and visited[nx][ny][flag] == 0:
queue.append([(nx,ny), flag])
visited[nx][ny][flag] = visited[x][y][flag] + 1
#벽일때
else:
if flag == 0:
queue.append([(nx,ny), 1])
visited[nx][ny][1] = visited[x][y][0] + 1
return -1
print(bfs(map_pos))
python3으로 채점했을때는 틀렸는데 pypy3으로 하니까 통과,,,,,,,,
알게된것
- bfs에서 최단거리를 구할때 queue에 count를 넣는 방법 말고 visited에 저장할 수도 있다!
Hongik CE