[백준 19236] 청소년 상어

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

19236번: 청소년 상어

#include <iostream>
using namespace std;

#define fastio() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

// 청소년 상어

struct fish {
    int r;
    int c;
    int direction;
    bool isAlive;
};

typedef pair<int, int> point;
int answer;
int map[4][4];
fish fishs[17];
point dir[9] = {{0, 0}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};

bool isPossible(point p) {
    
    // 칸을 넘어가면 이동할 수 없다
    if(p.first < 0 || p.first >= 4 || p.second < 0 || p.second >= 4)
        return false;

    // 상어가 있는 위치는 이동할 수 없다
    if(map[p.first][p.second] == -1) return false;
    
    return true;
}

void moveFishs() {
    
    for(int i = 1; i<=16; i++) {
        fish &cur = fishs[i];
        if(!cur.isAlive) continue;
        int d = cur.direction;
        point next = {cur.r + dir[d].first, cur.c + dir[d].second};
        
        int check = d;
        bool flag = false;

        while(!isPossible(next)) {
            d++;

            // 만약 360도를 돌았는데도 이동할 수 없다면
            if(d == check) {
                flag = true;
                break;
            }
            if(d > 8) d = 1;
            
            next = {cur.r + dir[d].first, cur.c + dir[d].second};
            cur.direction = d;
        }
        
        if(flag) continue;
        
        // 만약 이동하려는 칸이 빈 칸인 경우
        if(map[next.first][next.second] == 0) {
            map[next.first][next.second] = map[cur.r][cur.c];
            map[cur.r][cur.c] = 0;
            cur.r = next.first;
            cur.c = next.second;
            continue;
        }
        
        fish &temp = fishs[map[next.first][next.second]];
        swap(cur.r, temp.r);
        swap(cur.c, temp.c);
        swap(map[cur.r][cur.c], map[temp.r][temp.c]);
    }
    
}

void copy_map(int a[4][4], int b[4][4], fish c[17], fish d[17]) {
    
    for(int i = 0; i<4; i++)
        for(int j = 0; j<4; j++)
            a[i][j] = b[i][j];
    
    for(int i = 1; i<=16; i++)
        c[i] = d[i];
}

void solve(int r, int c, int d, int sum) {

    answer = max(answer, sum);
   
    int temp_map[4][4];
    fish temp_fishs[17];
    copy_map(temp_map, map, temp_fishs, fishs);
    
    moveFishs();

    for(int i = 1; i<=3; i++) {
        int rr = r + dir[d].first * i;
        int cc = c + dir[d].second * i;
        
        if(!(rr < 0 || rr >= 4 || cc < 0 || cc >= 4))
        {
        
            if(map[rr][cc] == 0) continue; // 만약 빈 칸이라면
            
            fish &f = fishs[map[rr][cc]];
            int n = map[rr][cc];
            map[r][c] = 0;
            map[rr][cc] = -1;
            f.isAlive = false;
            
            solve(rr, cc, f.direction, sum + n);
            
            map[r][c] = -1;
            map[rr][cc] = n;
            f.isAlive = true;
        }
        // 가는 도중에 벽을 만나면 더 이상 이동해보지 않음
        else break;
    }
    
    copy_map(map, temp_map, fishs, temp_fishs);
    
}

int main() {
    
    fastio();
    
    int idx, d;
    
    for(int i = 0; i<4; i++)
        for(int j = 0; j<4; j++) {
            cin >> idx >> d;
            fishs[idx] = {i, j, d, true};
            map[i][j] = idx;
        }

    idx = map[0][0];
    d = fishs[map[0][0]].direction;
    fishs[map[0][0]].isAlive = false;
    map[0][0] = -1;
    
    solve(0, 0, d, idx);
    
    cout << answer << endl;
    
    return 0;
}

오랜만에 푼 문제중 역대급이었다..

그 어떤 문제보다도 조건을 잘 읽어야한다는 걸 절실히 느끼게 해준 문제 ㅋㅋㅋ

1차적으로 생각한 것은 시뮬레이션 문제다. 빡구현이다.

그리고 상어의 움직임 경우는 백 트래킹으로 구해야 된다. 정도를 느끼고 구현을 시작했다.

하… 일단 데리고 다녀야 할 친구들이 정말 많다.

 

상어의 위치, 먹은 양.

물고기 인덱스 별 물고기의 위치와 물고기가 이미 먹혀있는지. (물고기는 인덱스 순서대로 움직이기 때문에)

맵에 대한 정보 (빈 칸인지 아닌지 구별해야 함)

 

이걸 어찌저찌 구현하고 보니 이동 조건을 잘 못 읽어서 엄청나게 헤맸다.

 

물고기 : 인덱스 순으로 이동한다.

이동이 불가능하면 반 시계 방향으로 45도 회전하여 방향을 바꾼다.

상어가 있는 위치에는 이동할 수 없다.

빈 칸으로는 이동할 수 있다.

(당연하게도 이미 먹힌 물고기는 이동할 수 없다)

모든 방향을 탐색하고도 이동할 수 없다면 물고기는 이동하지 않는다.

 

상어 : 먹은 물고기의 방향을 그대로 가지고 이동한다.

그러나 빈 칸으로 이동할 수 없다. (즉, 빈 칸을 건너 띄고 2방향을 갈 수 없다. 가는 길에 빈 칸이 있다면 그대로 정지)

이동이 불가능하면 (벽을 만나거나 빈 칸을 만나면) 방향을 바꾸지 않고 그대로 멈춘다.

 

이 조건을 완전히 이해하고 푼다면 사실상 시뮬레이션 + 백 트래킹이기 때문에 오래걸릴 뿐 풀 수 있던 문제였던 것 같다…

하지만 함정에 빠지면 디버깅하는 게 정말 역대급이었던 듯..