문제풀이5_BFS) 아기상어

Intro

코딩테스트 대비 문제풀이,

문제 링크를 첨부한다.

https://www.acmicpc.net/problem/16236

문제를 간략하게 설명해보면,

N * N 의 그래프가 주어진다.

0은 빈칸, 1~6는 물고기의 크기, 9는 아기상어가 된다.

아기상어가 그래프를 돌아다니면서 물고기를 잡아먹게 되는데, 물고기를 자신의 크기 수 만큼 잡아먹으면 상어가 레벨업을 하게된다.

물고기를 잡아먹기 위해 돌아다니는 아기상어의 이동 시간을 답으로 구하는 문제이다. 몇가지 조건들이 있는데 풀이과정과 함께 설명한다.

Solution

구현 방식을 설명해보면,

현재 아기상어 위치를 기준으로 bfs를 돌린다.

조건을 만족하는 위치의 물고기를 잡아 먹었다면, 그 위치를 기준으로 다시 bfs를 돌린다.

가장 짧은 시간동안 이동해서 잡아먹을 수 있는 물고기를 찾았을 때 바로 잡아먹으면 안되고, 

같은 시간으로 잡아먹을 수 있는 다른 물고기 까지 모두 탐색한 이후에 조건에 만족하는 물고기를 골라서 잡아먹어야 한다.

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

Code

Conclusion

조건도 체크하고, 머리도 열심히 굴려서 구현한 다음에 돌려보면, 항상 한번에 맞는 적이 없다.

모든 문제가 한번 풀고 난 다음에 에러를 수정해야 하는데, 어떤 문제는 어디서 에러가 났는지도 모르겠고 한참을 시간만 날리게된다.

이 문제도 초기에 코딩을 완벽하게 하지 못했기 때문에, 에러 잡는데 많은 시간을 사용했다.

꼼꼼하게 조건을 설정하는 것이 정말 중요한 것 같다.