[ BOJ - 19236번 ] 청소년 상어 (C++)

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

 상어가 더 이상 이동할 수 없을 때까지 물고기를 먹는 모든 조합을 탐색해야 한다. 처음 한 마리를 먹은 후 시작하여 최대 15마리를 추가로 먹을 수 있고, 상어가 이동할 수 있는 경로의 길이는 최대 3이기 때문에 상어가 한 번 이동할 때 경로 상 존재할 수 있는 물고기의 수는 최대 3마리이다. 따라서 물고기의 이동과 상어의 이동을 재귀함수로 구현하여 상어가 더 이상 움직이지 못할 때까지 반복하여 탐색하도록 구현한다면, 물고기의 이동에 15번 x 상어의 이동에 최대 약 400만번(3¹³x 2 x 1)의 연산이 필요하게 되어 시간 초과가 발생하지 않을 것이라 생각하고 문제를 풀었다. 

 

[ 풀이 방법 ]

1. 물고기 이동 기능

  1. 물고기 크기 순서대로 지정된 방향(상하좌우, 대각선)으로 물고기를 이동한다.

  - 물고기의 크기를 인덱스로 하여 물고기의 위치(x, y)와 방향(dir)을 멤버 변수로 갖는 구조체를 담는 vector(fish)를 생성하고,

    index (1 <= index <= 16)를 순회하며 각 물고기의 이동을 처리하도록 구현한다.

  - 물고기 이동은 물고기의 크기를 담는 2차원 배열(board)에 물고기의 갱신된 위치를 표시하고, fish 배열에서 물고기 크기에 해당하는 위치에 담긴 물고기 구조체의 위치와 방향 변수를 적절히 갱신하여 구현한다.

  - 물고기가 이동할 위치가 빈칸 또는 다른 물고기가 있는 칸이어야만 이동이 가능하다.

 

  2. 만약 물고기가 이동할 위치에 다른 물고기가 있다면 위치를 서로 바꿔준다.

 

  3. 만약 물고기가 이동할 위치에 상어가 있거나 경계를 벗어나 이동할 수 없는 경우, ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 순서로 방향을 회전하여 이동할 수 있는 위치로 이동한다.

  - 위 순서대로 dirR[8], dirC[8] 배열을 만들고 dir = (dir+1)%8로 반시계 방향 회전을 구현한다. 

int dirR[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dirC[8] = {0, -1, -1, -1, 0, 1, 1, 1};

int r = fish[size].r;
int c = fish[size].c;
int dir = fish[size].dir;
        
// 이동 가능한 방향을 바라보도록 반시계 방향으로 회전
for (int i = 0; i < 8; i++) {
    int nr = r + dirR[dir];
    int nc = c + dirC[dir];
            
    if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) {
        dir = (dir+1)%8;
    }
    else if(aux[nr][nc] == SHARK) dir = (dir+1)%8;
    else break;
}

 

2. 상어 이동 기능

  0. 상어는 처음 (0, 0) 위치의 물고기를 먹고, 해당 위치에서 먹은 물고기의 방향을 바라보며 이동을 시작한다(x, y, dir, sum을 멤버 변수로 갖는 구조체 shark로 저장).

 

  1. 상어의 방향에 해당하는 경로를 탐색하며, 물고기가 있는 위치로 이동하는 경우를 재귀함수를 이용하여 모두 탐색한다.

 

  2. 상어의 이동은 물고기의 이동과 비슷하나, 물고기가 있는 칸으로만 이동이 가능하다.

 

  3. 먹은 물고기를 표시하여 다음 재귀함수에서 해당 물고기의 이동이 생략되도록 구현한다.

 

  4. 먹은 물고기의 위치로 상어의 위치를 갱신하고(board, shark), 먹은 물고기의 크기를 sum에 더한 뒤 최대값과 비교하여 최대값을 갱신한다.

 

3. 상어가 먹을 수 있는 물고기 크기 합의 최대값을 구하는 기능

  1. 2-4번을 통해 구현한다.

 

위 기능들을 계획대로 올바르게 구현, 디버깅하여 문제를 해결할 수 있었다.

 

[ 회고 ]

 예제 입력 3번과 4번의 결과가 올바르게 나오지 않아, 이유가 무엇인지 디버깅하는 데 시간이 오래 걸렸다.

출력 결과를 확인하며 오류가 발생하는 이유를 찾으려 하였으나, 확인해야 하는 경우의 수가 너무 많고 출력 결과가 복잡하여 시간을 오래 사용하고 찾지 못하였다. 시간을 허비한 후에야 마지막으로 계획해 둔 접근 방법과 구현 방법대로 실수없이 올바르게 구현했는지 확인하였고, 구현할 때 실수로 빠뜨린 로직(먹은 물고기를 표시)을 찾을 수 있었고, 다음 로직을 추가해 문제를 해결할 수 있었다.

fish[eatenSize].eaten = false;

 

 결과적으로 계획해 둔 접근 방법과 구현 방법대로 실수없이 올바르게 구현했는지 확인하지 않고, 출력 결과를 바탕으로 디버깅하려 시도하여 정답을 맞추는 데 시간이 오래 걸렸던 문제였다.

 

 이번 문제의 경우 접근 방법과 구현 방법을 확실히 계획한 뒤 구현을 시작하였으나, 구현을 마친 뒤 모든 계획을 실수 없이 구현하였나 검증하지 않아 문제 해결에 어려움을 겪었다. 구현 방법을 확실히 계획한 뒤 구현을 시작한 것은 발전한 부분이나, 앞으로는 구현한 코드를 검증하는 단계를 반드시 거쳐야 할 것이다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

#define SHARK 17

using namespace std;

struct Fish {
    int r; int c;
    int dir; bool eaten;
};

struct Shark {
    int r; int c;
    int dir; int sum;
};

int dirR[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dirC[8] = {0, -1, -1, -1, 0, 1, 1, 1};


int res;

void rec(vector<vector<int>>& board, vector<Fish>& _fish, Shark& shark) {
    
    vector<vector<int>> aux(board.begin(), board.end());
    vector<Fish> fish(_fish.begin(), _fish.end());
    
    for (int size = 1; size <= 16; size++) {
        
        // 이미 먹힌 물고기 생략
        if(fish[size].eaten) continue;
        
        int r = fish[size].r;
        int c = fish[size].c;
        int dir = fish[size].dir;
        
        // 이동 가능한 방향을 바라보도록 반시계 방향으로 회전
        for (int i = 0; i < 8; i++) {
            int nr = r + dirR[dir];
            int nc = c + dirC[dir];
            
            if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) {
                dir = (dir+1)%8;
            }
            else if(aux[nr][nc] == SHARK) dir = (dir+1)%8;
            else break;
        }
        fish[size].dir = dir;
        int nr = r + dirR[dir];
        int nc = c + dirC[dir];
        
        // 이동 불가능한 경우 이동하지 않는다.
        if(nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue;
        else if(aux[nr][nc] == SHARK) continue;
        
        // 물고기 이동할 칸에 물고기가 있다면 위치 교환,
        // 물고기 이동할 칸에 물고기가 없다면 위치 갱신
        if(aux[nr][nc] != 0) {
            aux[r][c] = aux[nr][nc];
            fish[aux[r][c]].r = r;
            fish[aux[r][c]].c = c;
        } else {
            aux[r][c] = 0;
        }
        
        aux[nr][nc] = size;
        fish[size].r = nr;
        fish[size].c = nc;
    }
    
    
    int dir = shark.dir;
    int r = shark.r;
    int c = shark.c;
    int nr = r + dirR[dir];
    int nc = c + dirC[dir];
    
    // 상어가 이동하는 모든 경우 탐색
    while(true) {
        if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) {
            break;
        }
        if(aux[nr][nc]) {
    
            // 이동할 위치의 물고기를 먹고 상어의 위치와 방향, 먹은 물고기 크기의 합을 갱신
            int eatenSize = aux[nr][nc];
            fish[eatenSize].eaten = true;
            
            aux[nr][nc] = SHARK;
            aux[r][c] = 0;
            
            shark.r = nr;
            shark.c = nc;
            shark.dir = fish[eatenSize].dir;
            shark.sum += eatenSize;
            res = max(res, shark.sum);
            
            rec(aux, fish, shark);
            
            aux[r][c] = SHARK;
            aux[nr][nc] = eatenSize;
            
            shark.r = r;
            shark.c = c;
            shark.dir = dir;
            shark.sum -= eatenSize;
            
            fish[eatenSize].eaten = false;
        }
        nr += dirR[dir];
        nc += dirC[dir];
    }
    
    vector<Fish>().swap(fish);
    vector<vector<int>>().swap(aux);
}

void solve(vector<vector<int>>& board, vector<Fish>& fish) {
    fish[board[0][0]].eaten = true;
    Shark shark = {0, 0, fish[board[0][0]].dir, board[0][0]};
    board[0][0] = SHARK;
    
    rec(board, fish, shark);
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    vector<vector<int>> board(4, vector<int>(4));
    vector<Fish> fish(17);
    
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int size, dir;
            cin >> size >> dir;
            dir--;
            board[i][j] = size;
            fish[size] = {i, j, dir, false};
        }
    }
    
    solve(board, fish);
    
    cout << res << '\n';
    
    return 0;
}