[DFS와 BFS] [Python / C++] 2206. 벽 부수고 이동하기.

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

---

해결 방법

최단 경로 문제이다.

이 문제를 처음 접했을 때는 DFS로 풀어야하는 줄 알았다.

벽을 부셨는지 확인하는 bool 변수를 하나 선언하고 부신 경우 다음 지점이 0인 경우 앞으로 나아가도록 구현하려고 했었다.

근데 뭔가 이상하게 흘러가는 것을 깨닫고 질문 게시판을 참고하던 도중 알고리즘 고수분의 정리글을 보게 되었다.

최단 거리 혹은 최단 경로 문제에서 되게 자주 보이는 괴수분인데 아무튼...

 

첫 번째 문장을 읽고 생각이 짧았음을 바로 인지했다... 이후 DFS에서 BFS로 변경했고 다시 생각해보았다.

 

핵심은 해당 지점까지의 최단 경로를 저장하되, 벽을 부신 경우 이동하려는 지점이 0인 경우에만 이동할 수 있다는 것이다.

 

조건을 정리해보면

1. 다음 이동할 곳이 벽이고, 벽을 부술 수 있는 경우

-> 벽을 부수고 다음 지점으로 이동하고 벽을 부술 수 있는 횟수를 0으로 만들어준다.

 

2. 다음 이동할 곳이 길인 경우 (= 0)

-> 다음 지점으로 이동하고 이전 지점까지의 거리 + 1을 해준다.

 

이렇게 코드를 구현해서 제출을 했는데

엥 시간초과...?

 

이후 코드를 다시 봤는데 조건을 잘못 설정해줬었다.

 

문제는 2번 조건이였다. 나는 단순히 다음 이동할 곳이 길인 경우만 조건에 넣어줬는데 이 경우에 이전 지점을 다시 방문하게 되는 오류가 발생한다. for문을 통해 상, 하, 좌, 우 4개의 방향으로 한칸씩 나아가고 있는데 만약 현재 지점도 0, 다음 지점도 0인 경우 무한 루프에 빠져버릴 수가 있다. (아래로 내려갔다가 다시 위로 또 다시 아래로... 무한 반복) 다음 이동할 곳의 최단 거리가 0인 경우, 즉 아직 방문하지 않은 경우 다음 지점으로 넘어가도록 조건을 추가해줬고 통과할 수 있었다.

 

 

조건을 다시 정리해보면

1. 다음 이동할 곳이 벽이고, 벽을 부술 수 있는 경우

-> 벽을 부수고 다음 지점으로 이동하고 벽을 부술 수 있는 횟수를 0으로 만들어준다.

 

2. 다음 이동할 곳이 길이고 (= 0), 다음 지점이 방문하지 않은 지점인 경우

-> 다음 지점으로 이동하고 이전 지점까지의 거리 + 1을 해준다.

 

위 조건에 따라 계속 반복하다가 dst에 도착하면 저장된 최단 거리를, 도착할 수 없는 경우에는 -1을  리턴하게 구현해주었다.

 

우선 위의 개념을 파이썬으로 구현해봤다.

 

 

C++로도 구현해봤다. 요즘에 파이썬만 쓰다보니까 머리가 파이썬화 됐나보다...

C++ 너무 어려운듯... 지역변수로 선언하니까 Segment Fault도 뜨고... 아무튼 애먹었음 ㅎㅎ;;

확실히 퍼포먼스는 따라올 수 없는듯? 50배나 빠르다...ㄷㄷㄷ

 

 

ㅋㅋㅋㅋ cin에서 부터 오류떴음...

 

 

역시 골드문제인가... 좀 더 생각하게 만드는 문제다.