[BOJ] 탈출_3055

 

이 문제는 풀이 방법이 바로 떠올라서 풀었지만, 효율성이 완전 꽝이였다.

그리고 그 효율성 꽝인 코드 마저 문제를 잘못 읽어 틀렸었다.

r,c이 행과 열 같지만, 예제 입력을 보면 그 반대라는 것을 알 수 있다. (약간 말 장난 아닌가 싶긴 했다 ㅠㅠ, 그래도 다음 번엔 문제 꼭 잘 읽자.)

 

풀이 방법

1. water()로 물을 한 번만 퍼트린다.

2. beaver_move()로 비버를 한 번 움직인다.

비버가 목적지에 도달하면 멈추고, 비버 큐가 비어있어도 멈춘다.

비버 큐가 비어있어서 멈추는 것은 도달하지 못한다고 가정하고 "KAKTUS"를 출력해준다.

 

후기

이 문제의 핵심은 beaver_move()와 water()에서 큐를 for으로 돌리는 것 같다.

보통 기존의 풀던 bfs()와는 달리, 한 턴에 한 번씩만 돌아야 하기 때문에 그냥 whlie q:를 써버리면 안된다.

아까 효율성 꽝이었던 코드는 맵 전체를 돌면서 물을 계속 큐에 삽입해주는 것이였다.

이걸 해결하기 위해 큐의 len을 구하여 그 만큼만 구해주었다.

 

이렇게 한 턴에 한 번씩만 돌아가는 방식을 구현하는 것은 2가지 방법이 있다.

위 코드처럼 len을 활용하여 반복문을 도는 것과, 큐에 첫 번째 지점으로 부터 떨어진 값을 활용하는 것이라고 한다.

근데 후자의 방법은 어떻게 하는지 모르겠으니 지금 공부해보자.