[BOJ2206] 벽 부수고 이동하기

문제

• NxM 행렬 0이동 1벽
• (1,1) —> (N,M) 최단경로
• 벽 하나만 부술 수 있음

입력

• 첫째 줄 N, M (1<= <= 1,000)
• 다음 N줄 M개의 숫자로 맵 주어짐

출력

• 최단거리 출력, 불가능시 -1

설계

• 최단거리를 구하는 문제이기 때문에 BFS 적용
• visit 변수를 단순 2중배열로 처리하는 것이 아니라, 3중 배열사용
• visit 3번째 배열은 벽을 부순 경우와 안 부순 경우의 두 가지 상황에 대한 처리 하기 위함. 그래서 크기는 2
• 위의 처리를 안 해줬을 때, 주어진 테스트케이스는 통과하지만 안 되는 예 (벽을 부수고 먼저 특정 좌표에 visit 처리를 해주면, 안 부수고 돌아가는 경우 길이 막힐 수 있음)

  6 3
  000
  110
  000
  011
  111
  000
  

• Bfs에서 queue의 매개변수로 벽을 부쉈는지 체크하는 bool(default : false) 넣어주고, 처음 만난 벽을 부수고 true로 변경 후 visit 변수에도 적용

피드백

• 처음에는 모든 1에 대해 0으로 한 번씩 바꿔주고, 각각의 상황에서 bfs를 돌렸음 —> 시간초과
• 심지어 bfs 처리도 좌표를 queue에 넣자마자 방문 처리를 해줘야 메모리 효율을 높일 수 있는데, 좌표에 방문 후 방문처리를 하여 메모리 초과 뜸
• 당연히 visit변수는 2차원으로 풀려고 계속 노력했지만 안 됨… 히든 테스트케이스 못 찾겠어서 포기함 (설계의 예제 케이스)
• 생각보다 그래프 문제가 아직도 약함

How I solved(click to github)

---

ref :
BOJ2206
참고한 다른 블로그