[백준] 9376번: 탈옥 - 파이썬

문제 보기

 

https://www.acmicpc.net/problem/9376

9376번: 탈옥

 

 

 

---

풀이 및 코드

 

bfs, dfs 문제들 많이 풀어서 코드 짜는 게 오래 걸리지는 않지만, 해당 문제는 풀이가 어려웠다. 오랜 시간 고민하고 삽질하다가 다른 분들 코드를 보고 공부하고 나서 풀었다..

 

 

알고리즘은 다음과 같다. 

 

 

수감자들의 위치에서 그리고 상근이의 위치에서 각각 bfs를 돌린다. 그러면 3명을 위치를 기준으로 출발했을 때 특정 위치까지 가기 위해서는 얼마나 문을 열어야 하는지에 대한 정보를 얻을 수 있다. 이제 그것들을 더해 주자. 그러면 그 값은 세명의 인물이 해당 위치에 모이기 위해 문을 얼마나 열었는 지를 나타낸다. 하지만 이 값은 중복제거를 하지 않은 값이다. 1번 수감자에 대한 정보는 상근이와 1번 수감자가 사전에 문을 열었는 지를 내포하지 않는다. 즉 더해진 값은 특정 문을 여러번 열었는 지에 대한 정보가 들어있지 않다. 따라서 최소가 되는 위치의 값을 가져와야 한다. 최소라는 뜻은 문을 중복해서 열지 않았다는 의미이기 때문이다. 여러번 문을 여는 행위를 막자는 의미이다. 만일 가장 작은 숫자의 위치가 문이라면 -2를 해주자. 문의 위치에 저장된 값은 문을 열었다고 가정해 있기에 -2를 해 3명중 한명만 문을 열었다고 계산하면 된다.

 

 

마지막으로 밖에서 들어오는 상근이는 어떤 위치에서 들어올지 알 수 없다. 따라서 bfs를 원활하게 진행하기 위해 빈칸으로 상하좌우를 한칸씩 더해주자. 그렇다면 상근이 입장에서 bfs를 하기에 훨씬 수월하다!

 

 

 

 

 

 

 

 

 

 

 

개인적으로 도움이 많이 되었던 포스팅이다.

https://rebas.kr/770