백준 2206 문제 링크: https://www.acmicpc.net/problem/2206
📑 문제 설명
1. NxM 행렬이 주어짐
2. 행렬 내에서 0은 이동할 수 있는 곳, 1은 벽으로 이동할 수 없음
3. (1, 1) 위치에서 시작하여 (N, M)으로 도착하는 최단 거리를 구해야 함
4. 그러나 벽을 부수고 갈 때 이동거리가 훨씬 짧아진다면 1회만 벽을 부술 수 있음
체크 포인트
1. 상하좌우로만 이동 가능하며 이동 시 1씩 추가됨
2. 시작점과 끝점에 도달할 경우에도 1씩 추가됨(이동거리 + 시작점 + 끝점)
입력: 첫번째 줄에 N, M이 주어지고 두번째 줄부터 행령이 주어짐
출력: 최단 거리
💡 문제 해결 방법
알고리즘: BFS
알고리즘 선택 이유
1. 최단거리를 구하는 문제이므로 BFS 사용
2. 벽을 부신 것에 대한 여부를 체크해야 함 --> 이 때 visit 배열을 3차원으로 만들어 queue에서 pop한 원소가 벽을 이미 한 번 부시고 방문하는 상태인지, 아니면 아직 벽을 부시지 않은 상태인지 체크
예외처리
1. DFS 종료 조건: N,M에 도달하거나 도달할 방법이 없을 경우 --> 경로가 없을 경우
2. 벽을 부셨는지 여부를 저장하는 변수 설정
스터디 내용
- 14442번이 벽 부수고 이동하기 --> k번 부술 수 있음
- 입력에 공백이 없으므로 캐릭터로 읽어야 함 --> 공백 여부 확인하기
- BFS
- x, y brakeable(벽 부수는 여부), dist 값을 체크해야 함
- make tuple로 한 번에 묶어서 입력
💻 코드
import sys
from collections import deque
n, m = list(map(int, sys.stdin.readline().split()))
graph = [[0 for x in range(m)] for x in range(n)]
for i in range(n):
temp = sys.stdin.readline()
for j in range(m):
graph[i][j]= int(temp[j])
visit = [[[False, False] for x in range(1002)] for x in range(1002)]
def bfs():
queue = deque([(0, 0, 0, 0)]) # x, y, break 횟수, dist
visit[0][0][0] = True
visit[0][0][1] = True
while(queue):
x, y, breakable, dist = queue.popleft()
if x == n-1 and y ==m-1:
print(dist+1)
return
adj_list = [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]
for point in adj_list:
nx, ny = point
if nx >=0 and nx<n and ny>=0 and ny<m and visit[nx][ny][breakable] == False:
if graph[nx][ny] == 0:
visit[nx][ny][breakable] = True
queue.append((nx, ny, breakable, dist +1))
else:
if breakable == 0:
visit[nx][ny][breakable] = True
queue.append((nx, ny, 1, dist+1))
print(-1)
bfs()💟 추가적으로 알게 된 점
- 이 문제의 핵심은 visit 배열이 3차원으로 구성되어 지금 내가 방문하는 버택스가 벽을 부시고 온 상황인지 아니면 아직 부시지 않고 방문한 상황인지 캐치
- queue에는 반드시 x, y 좌표만 들어갈 필요가 없다...
- visit 배열이 반드시 2차원일 필요가 없다...
- deque에 여러 원소를 한 원소로 묶어서 넣을 때는 tuple 형식으로 append 해주면 된다...
- list보다 속도가 더 빠르니 참고 - bfs에서 방문 기록을 잘못 체크할 경우 queue에 한 버택스가 중복으로 들어가 메모리 초과가 날 수 있으니 방문을 하는 조건을 꼼꼼히 생각해서 처리해주어야 한다.
