[BOJ] 19237 어른 상어 (C/C++)

19237번: 어른 상어

---

보통 내용도 붙여 넣는데 이 문제 같은 경우엔 문제가 너무 길어서 따로 붙이지 않았다. 

 

문제를 풀기 위해서 두 가지 자료구조가 필요하다고 생각했다. 그래서 상어들의 현재 상태를 저장하고 있는 구조체와 냄새의 현재 상태를 저장하는 구조체를 만들었다.

첫 번째 구조체는 다른 알고리즘 문제들과 비슷하게 현재 상어의 좌표와 방향, 생존 여부가 들어있다. 이 문제가 특이한 점은 각 상어마다 이동 방향의 우선순위가 다르다는 것이었다. 2차원 배열을 사용해서 상어마다 상이한 우선순위를 저장했다.  두 번째 구조체는 어떤 상어가 냄새를 남겼는지와 언제 남겼는지를 저장한다. 이후에 이 "언제" 정보를 사용해서 냄새를 지운다.

 

이 문제의 순서는 다음과 같다.

초기 상태(0초)	현재 상어가 있는 좌표에 냄새를 남긴 상태
진행 과정(1~1000초)	1. 상어 이동 2. 이동한 좌표에 냄새 남김 3. 냄새 지움
완료	1번 상어만 남음

따라서 과정마다 필요한 냄새 남기는 함수, 상어 이동 함수, 냄새 지우는 함수를 만들어 사용했다. 냄새를 남기거나 지우는 함수를 구현하는 것은 그렇게 어렵지 않았다.

 

하지만 상어를 움직이는 함수는 꽤나 까다로웠다. 상어는 우선 주변에 냄새가 없는 공간이 있는지 찾는다. 이런 공간이 있다면 그곳으로 움직이지만 없다면 주변에서 자기 자신의 냄새가 나는 공간으로 이동한다. 이때 모두 상어 각각의 우선순위가 적용되어야 한다. 그리고 같은 좌표에 둘 이상의 상어가 있다면 번호가 큰 상어는 제외된다. 번호가 큰 상어를 제외시키기 위해서 임시 배열을 사용하여 이미 좌표에 상어가 있다면 그 상어는 제외되는 식으로 구현했다. 왜냐하면 번호가 작은 상어부터 이동시키기 때문에 이미 움직인 상어와 같은 좌표라면 그 상어는 무조건 제외되어야 하기 때문이다.

 

후기)

다른 상어 문제들에 비해서 쉬웠던 것 같다. 저번에 풀었던 상어 문제들은 진짜 구현할 내용이 너무 많다고 느꼈는데 이 문제는 자료구조만 제대로 짠다면 구현 내용 자체가 많지는 않았던 것 같다.