A. 문제설명
https://www.acmicpc.net/problem/19236
문제에 대한 자세한 설명은 링크 참조
1. 4*4 배열공간에 물고기의 번호와 방향이 각각 주어짐
2. 물고기의 방향은 1~8로, 12시방향부터 45도씩 반시계방향으로 각각 회전하여 주어짐
3. 이 배열공간 안 (0,0) 위치에 상어가 들어가 사냥을 시작
4. 상어는 (0,0) 위치의 물고기를 먹고 해당 물고기의 방향을 가짐
5. 이후 번호 순서대로 물고기가 이동, 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸이다. 현재 방향에서 이동하지 못할 경우 반시계방향으로 45도씩 회전하며 이동할 공간을 찾음
6. 물고기의 이동이 끝나면 다시 상어가 이동, 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동가능
7. 상어는 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 최종적으로 상어가 먹을 수 있는 물고기 번호의 합의 최대를 구하라
B. 접근법
DFS(백트랙킹) + 시뮬레이션
우선, 문제에서 상어가 이동하는 모든 경우에 대해서 DFS로 탐사해야 한다.
그러나, 여기서 염두해 두어야 할 부분이 있다. 상어가 물고기를 사냥하고, 물고기가 이동하는 경우 전체 배열에서의 물고기의 배치가 완전히 바뀌어 버리는 데, 이를 깊이우선 탐색으로 호출 시, 원복할 수 있도록 고려해서 구현하여야 한다.
위 dfs_shark() 함수 코드에서, 7번 라인의 copy_arr(arr, tmpArr, fishArr, tmpFishArr); 은 DFS 호출 이전 현재 상태를 스냅샷처럼 현재 함수 스택에 복사해 놓는 로직이다.
여기서, 21번 라인의 코드로 돌아가 다음 상어가 먹을 물고기의 위치에 상어를 놓고 해당 물고기가 죽은 것을 표시하고 재귀 호출에 들어간다. 그리고는, 27번 라인에서 해당 함수의 호출이 끝난 경우 해당 물고기의 상태를 다시 원복시킨다.
마지막에 27번 라인에서 copy_arr(tmpArr, arr, tmpFishArr, fishArr); 의 코드가 물고기 배열의 상태를 원복시키는 부분이다.
그리고, 상어의 DFS 함수 구현부에서는 물고기가 이동하는 시뮬레이션을 구현한 move_fish() 함수를 호출한다.
여기서 물고기는 상어가 없는 자리의 물고기의 자리나 빈 자리로 이동해야 하며, 현재 방향에서 이동하지 못할 시, 8방향을 모두 확인하며 회전하여 탐사해야 한다.
C. 풀이
1. (0,0) 위치로 상어를 넣고 DFS 탐사 시작
2. 해당 위치에 들어간 상어는 해당 물고기의 방향을 가짐
3. 해당 방향에서 갈 수 있는 모든 경우에 대해, 다시 재귀적으로 탐사함
4. 재귀 호출에서 빠져나온 상어와 물고기 상태를 원래로 원복
5. 매 상어의 이동시마다 물고기도 따라 이동하는 데
5-1. 1번 물고기부터 16번 물고기까지 모든 물고기 이동 시작
5-2. 물고기는 이동할 수 있을때까지 8-방향을 전환해가며 반복
5-3. 만약 해당 위치에 다른 물고기가 있을 시, 현재 물고기와 해당 위치의 물고기를 서로 바꿈
5-4. 해당 위치가 비어있을 시, 현재 물고기를 해당 위치로 옮김
5-5. 이동 불가능한 경우, 물고기 방향을 하나 회전하고 다시 반복 진행
6. 깊이우선 탐색을 통해 상어는 모든 경로를 다 탐사하고, 그 중 가장 먹이를 많이 먹은 경우를 출력
D. 내 코드
