백준 16236 - 아기 상어 (Python)

https://acmicpc.net/problem/16236 

16236번: 아기 상어

3달전, 처음 ps를 시작하고 3주차에 주제넘게 덤볐다가 포기한 문제.

​

이제는 쉽게 풀 수 있었다. 최대 그래프 크기가 20*20이니 사실상 시간 복잡도를 고려하는 문제라기보다는,

빡구현 문제임을 예상해 볼 수 있다. bfs인듯 아닌듯한 bfs 문제이다.

선언부에서는 문제의 조건대로 시간 (물고기를 먹는 순간의 시간), 물고기의 크기, 물고기의 크기가 증가하기 위해 먹어야 하는 개수의 상태(일종의 스택)을 저장한 후 초기 상태로 지정한다.

함수부가 핵심이다. 물고기를 먹기 위해 여러 조건을 꼼꼼하게 맞춰 구현한다.

그래프 범위 내 상하좌우 중, 방문하지 않은 지점 중, 크기가 나보다 작은 물고기만 먹을 수 있다.

물고기를 먹으면 count+1, count가 크기와 같으면 크기를 +1한다. 크기가 나와 같은 물고기는 지나친다.

여기서는 sorted가 핵심이다. 결국 도착할 수 있는 여러 지점 중에 ,

1. 가장 가깝고
2. 가장 위쪽에 있고
3. 가장 왼쪽에 있는

것을 lambda를 이용하여 순서대로 sort한 후 먹은 물고기는 0으로 바꾼다.

더 이상 먹을 것이 없을 때까지 계속한다. 끝난 뒤에 시간을 출력하면 정답이다.

​

벽을 뚫은 기분이다. 아직 수준이 부족하지만, 해결하지 못해 절망했던 문제를 스스로 해결하니 기분이 오묘하다.