#9328 열쇠
출처:https://www.acmicpc.net/problem/9328
9328번: 열쇠
문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. 각
www.acmicpc.net
각각의 문(영대문자)마다 맞는 열쇠(영소문자)가 있고 열쇠 획득시 같은 알파벳의 문은 몇개가 되든 계속 열 수 있다.
외부에서 침입하여 문을 열고 문서($)를 최대한 많이 갖고 나오는 문제이다.
두가지 방법으로 접근하여 풀었다.
첫 번째로 외부 (0,0)에서 시작하여 bfs로 맵 전체를 완전 탐색 후 획득한 열쇠들을 벡터나 큐에 저장한 후 해당 열쇠에 해당하는 문들을 모두 지도에서 제거한 후 다시 (0,0)에서 bfs로 맵 전체를 완전탐색하는 것을 열쇠 획득이 없을때까지 반복하는 것이다.
두 번쨰로는 같은방식인 bfs로 맵 전체를 탐색하다가 문을 열 수 없으면 일단 알파벳 별 문의 좌표를 저장할 수 있는 큐에 넣어둔다. 그러고나서 열쇠를 찾을 시에 문벡터를 열람하여 만약 해당 열쇠에 해당하는 문이 있으면 원래 탐색하는 q에 푸시한다. 그리고 해당 문벡터들은 열쇠가 있으므로 다 pop연산을 해줘야 한다. 이런식으로 하면 탐색 한번에 문서를 모두 찾을 수 있게 된다.
실제로 시간도 92ms 에서 4ms로 줄어들었다.
먼저 첫번째 방식의 소스코드다
다음은 두번째 방식의 소스코드
