백준 9376번 탈옥

문제 링크입니다: https://www.acmicpc.net/problem/9376

9376번: 탈옥

문자열 배열을 전역으로 놓은 상태에서 push_back을 해서 끊임없이 틀렸던 문제였습니다.

이런 유형의 문제는 적지 않게 출현하는 문제이므로 유형을 익혀놓으면 나중에 코딩테스트에서 도움이 될 것 같습니다.

 

알고리즘은 아래와 같이 세 가지 경우를 생각하면 됩니다.

1. 죄수 1이 죄수 2를 데리고 바깥으로 나가는 경우

2. 죄수 2가 죄수 1을 데리고 바깥으로 나가는 경우

3. 상근이가 죄수 1, 2를 찾으로 잠입하는 경우

 

따라서, 3명이 각자 탐색하다가 한 지점에 만날 경우 탈출을 했다고 봐도 무방합니다.

즉, 각 지점마다 죄수 1, 죄수 2, 상근이가 문을 연 횟수를 저장해 놓으면 나중에 문을 연 최소 횟수를 파악할 수 있습니다.

주의할 점은 한 곳에 모인 지점이 문일 경우 죄수 1, 죄수 2, 상근이 모두 문을 열었다고 계산되어 있는 상태이므로 -2를 빼줘야합니다.

또한, 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열기 때문에 입력 받은 감옥 주변을 빈칸으로 채워준 뒤 (0, 0)에서 출발하게 하면 됩니다.

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~