[BOJ] 9328 열쇠

litien·2019년 11월 14일
0

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

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

삽질 회고

문제를 읽으면서 중요하다 생각했던 부분은 시작 진입점과 문의 위치가 중요하다고 생각했다. 그래서 다음과 같이 알고리즘을 설계했다.

  1. 시작점을 벡터에 저장한다.
  2. 열쇠를 만났을 때, 대문자로 바꾸고 Map<char,bool> openDoor에 true 체크를 해준다.
  3. BFS 실행

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

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

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

profile
어려운 문제를 함께 풀어가는 것을 좋아합니다.

0개의 댓글