[백준] 19237 어른 상어

올해 삼성 역량테스트 문제로 알고 있다. 이 문제는 시키는 대로 구현하는 문제이다.

 

문제의 출처는 아래와 같다.

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

 

이 문제는 복잡한 구현으로 설계를 잘해야한다. 먼저 각 상어들을 구조체로 관리하여 위치와 방향, 그리고 살이있는지를 관리한다.

문제에서 방향에 따라 복잡하게 구현되어져 있는데 그것을 shark_dir[상어번호][방향][우선순위] 로 지정해 주었다.

사용방식은 sol() 함수의 내부를 보면 이해할 수 있다.

마지막으로 상어의 냄새와 해당 위치에서의 상어 번호를 관리해준다. (smoke[x][y][냄새],smoke[x][y][상어번호] )

이제 시뮬레이션은 아래와 같다.

 

0) 입력과 함께 해당 위치에서의 냄새 및 상어번호를 저장하고 상어 구조체의 모든 값을 저장해준다.

1) 각 상어를 이동시킨다. 이동은 문제에서 있는대로 구현하면 된다. sol() 함수 참조

  * 상어가 이동할 곳이 없을때, 자신의 냄새가 있는 곳으로 이동하는데 이동하고 방향을 어떻게 지정하라는지 문제에서 애매모호 하다. 이 부분은 디버깅을 통해 겨우 찾아냈는데.. 이동하는 것과 똑같이 방향을 해주면 된다...

 

2) 이동 후 냄새 유지시간을 1씩 없애준다. 냄새가 0이 된다면 그곳은 사라지니 상어번호도 함께 제거해준다.

 

3) 이동한 결과로 같은 위치의 상어들을 처리한다. 번호가 낮은 상어가 다 잡아먹는다. 먹힌 상어를 죽은것으로 바꿔줘야 한다. 그리고 이동한 위치에 새로 냄새를 뿌리고 상어번호를 넣어준다.

* 이 부분을 잘못 작성해 오류를 나타냈다. 번호가 작은 상어가 다 잡아먹도록 쉽게 구현하도록 한다. 

 

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
struct info {
    int x, y, dir, die;
}shark[404];
 
int n, m, k, arr[21][21], num, smoke[21][21][3], visit[401], Ans = -1;  // 1: 상어번호 2: 냄새남은시간
int dx[5] = { 0,-1,1,0,0 }, dy[5] = { 0,0,0,-1,1 };
int shark_dir[404][5][5]; // 1: 위 2: 아래 3: 좌 4: 우
 
void update() {
    for (int i = 1; i <= m; i++) {
        if (shark[i].die == 1) continue;
        for (int j = i; j <= m; j++) {
            if (i == j) continue;
            if (shark[i].x == shark[j].x && shark[i].y == shark[j].y) {
                if (i < j) shark[j].die = 1;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        if (shark[i].die != 1) {
            smoke[shark[i].x][shark[i].y][1] = i;
            smoke[shark[i].x][shark[i].y][2] = k;
        }
    }
}
 
void sol(int number) {
 
    int x = shark[number].x, y = shark[number].y;
    int chk = 0;
    int n_dir = shark[number].dir;
    for (int i = 1; i <= 4; i++) {
        int kx, ky;
        kx = x + dx[shark_dir[number][n_dir][i]];
        ky = y + dy[shark_dir[number][n_dir][i]];
        if (kx < 0 || kx >= n || ky < 0 || ky >= n) continue;
        if (smoke[kx][ky][2] != 0) continue;
        chk = 1;
        shark[number].x = kx, shark[number].y = ky;
        shark[number].dir = shark_dir[number][n_dir][i];
        break;
    }
    //cout << number << "  " << chk << endl;
    if (chk == 0) {
        for (int i = 1; i <= 4; i++) {
            int kx, ky;
            kx = x + dx[shark_dir[number][n_dir][i]];
            ky = y + dy[shark_dir[number][n_dir][i]];
            if (kx < 0 || kx >= n || ky < 0 || ky >= n) continue;
            if (smoke[kx][ky][1] == number) {
                shark[number].x = kx, shark[number].y = ky;
                shark[number].dir = shark_dir[number][n_dir][i]; // 이동할 곳이 없을때 방향을 이렇게 처리
                //if (shark[number].dir == 1) shark[number].dir = 2;
                //else if (shark[number].dir == 2) shark[number].dir = 1;
                //else if (shark[number].dir == 3) shark[number].dir = 4;
                //else if (shark[number].dir == 4) shark[number].dir = 3;
                break;
            }
        }
    }
    //for (int i = 0; i < n; i++) {
    //for (int j = 0; j < n; j++) {
    //printf("%d ", smoke[i][j][1]);
    //}
    //printf("\n");
    //}
    //printf("\n\n");
}
 
int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] != 0) {
                shark[arr[i][j]].x = i, shark[arr[i][j]].y = j;
                smoke[i][j][1] = arr[i][j], smoke[i][j][2] = k;
            }
        }
    }
 
    for (int i = 1; i <= m; i++) {
        int a;
        scanf("%d", &a);
        shark[i].dir = a;
    }
 
    for (int e = 1; e <= m; e++) {
        //cout << ans << endl;
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                int a;
                scanf("%d", &a);
                shark_dir[e][i][j] = a;
            }
        }
    }
 
    for (int w = 0; w < 1001; w++) {
        int ans = 0;
        for (int i = 2; i <= m; i++) {
            if (shark[i].die == 1) ans++;
        }
        if (ans == m - 1) {
            Ans = w;
            break; //1번 혼자 남으면 종료
        }
        for (int j = 1; j <= m; j++) {
            if (shark[j].die == 1) continue;
            sol(j);
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (smoke[i][j][2] > 0) smoke[i][j][2]--;
                if (smoke[i][j][2] == 0) smoke[i][j][1] = 0;
            }
        }
        update();
        //for (int a = 0; a < n; a++) {
        //for (int b = 0; b < n; b++) {
        //printf("%d ", smoke[a][b][2]);
        //}
        //printf("\n");
        //}
        //printf("\n\n");
    }
    cout << Ans;
    return 0;
}