벽 부수고 이동하기 [2206]

벽 부수고 이동하기 [2206]

백준 - https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

깃헙 - https://github.com/shs9509/study

문제

• 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을 출력한다.

---

틀린 풀이과정

• 못풀엇다!
• 밑에 맞는 풀이과정이 있다.
• bfs로 접근하고 벽을 뿌셧다는 표현인 falg를 통해서 나타내려고 했으나
• bfs가 돌면서 벽뚫고 갔는지, 안뚫고 가는지에 대해서 겹처서 사라지는 경우가 생긴다.
• 그래서 if 문 어떻게 어떻게 써서 해결하려고 했으나 실패!

 

---

맞는 풀이과정 

• bfs 와 flag를 쓰는것은 맞는 접근법이라 생각하엿고
• 답을 찾아본 결과, flag 를 쓰기보다 3차원배열로서 접근하였다.
• 즉슨, 2차원배열에서 벽을 뿌시면 다음 차원으로가서 길을 찾는다는것!
  • 벽 안뿌심 - 원래있던 미로에서 진행 , 뿌술기회 1번남았다고 생각하고 bfs 진행
  • 벽 뿌심 - 다른 미로로 시작(현재자리) 단 뿌술기회가 없다고생각하고 bfs 진행

• 3차원 배열이라고 생각하기보다 미로 두개를 가지고 bfs 를 돌렸다고 생각하면 편하다.
• 추가적으로 응용이 된다면 벽을 여러번 뿌실수있다고 생각하면 그만큼, 미로 개수를 늘리면 되는것!

 

 

• 사용된 코드 : https://pacific-ocean.tistory.com/348

[백준] 2206번(python 파이썬)

---

느낀점

• 상당히 어려운 문제였고, 처음에는 답을 봐도 이해하질 못했다.
• 나중에 설명을 듣고 이해를 하였는데 상당히 퀄리티있는 문제가 아닐까 생각된다.
• bfs 문제를 왠만해서는 풀수있겠다 생각했었지만 다시 나를 겸손하게 만든 문제였다.