[BOJ] 9328 열쇠

문제보기
코드보기
분류 : BFS
난이도 : 3.5 / 5

• 놓칠 수 있는 조건이 많아 실수하기 쉬운 문제다

삽질 회고

문제를 읽으면서 중요하다 생각했던 부분은 시작 진입점과 문의 위치가 중요하다고 생각했다. 그래서 다음과 같이 알고리즘을 설계했다.
1. 시작점을 벡터에 저장한다.
2. 열쇠를 만났을 때, 대문자로 바꾸고 Map<char,bool> openDoor에 true 체크를 해준다.
3. BFS 실행

여기에는 실수의 여지가 많다. 내가 코드를 작성하면 겪었던 실수는 다음과 같다

• 시작 지점을 제대로 벡터에 저장하지 못했다.
  - 바운더리에 있는 열쇠를 시작 지점에 넣지 않았다.
  • 바운더리에 있는 열 수 있는 문을 시작 지점에 넣지 않았다.
• 열쇠를 만나고 나면 문 위치로 순간이동 시켰다.
  - 열쇠를 만나고 나면 openDoor를 true로 바꾸고 que의 문 위치를 집어넣었다. --> <char, vector> doorPostion이라는 자료구조를 선언해, 지금까지 만난 문중 열지 못한 문을 가지고 있다가 열쇠를 만나면 해당 위치를 큐에 넣어준다.

위와 같은 문제점 특히 바운더리에 있는 열수 있는 문을 시작 지점에 넣지 않아 많이 해맸다. 또 중간에 코드로직이 계속 수정되다보니 다른 곳에서 또 문제가 발생하는 악순환이 반복됬다. 초기에 로직을 깔끔하게 설계하고 놓치는 조건이 있는지를 잘 체크하자.