[BOJ] 어른 상어

 

 

문제 링크

 

https://www.acmicpc.net/contest/problem/517/3

C번: 어른 상어

---

아이디어

시뮬레이션

 

문제에 주어진 로직을 정리하면 다음과 같다.

1. 생존한 상어들은 현재 위치에 냄새를 뿌린다.

2-1. 생존한 상어들은 우선순위에 따라 상하좌우 중 냄새 없는 칸으로 이동한다.

2-2. 인접한 칸에 냄새없는 칸이 없다면, 우선순위에 따라 상하좌우 중 자신의 냄새가 있는 칸으로 이동한다.

3. 이동한 칸에 여러 상어가 같이 있다면 가장 작은 번호의 상어만 생존한다.

4. 모든 칸의 냄새가 1씩 감소한다.

 

pos[i][j]        : (i, j)칸에 있는 상어의 번호

smell[i][j]      : (i, j)칸에 있는 냄새의 양

owner[i][j]     : (i, j)칸에 있는 냄새의 주인 (냄새를 뿌린 상어의 번호)

dead[i]         : i번째 상어의 생존여부

can_spread[i] : i번째 상어가 2-1단계에서 냄새 없는 칸으로 이동했는지 여부

 

---

주의할 점

• 상어가 빈 칸으로 이동할 때 같은 칸으로 이동한 상어들은 작은 번호빼고 모두 다음 time에 사라지기 때문에
  큰 번호의 상어부터 이동시키면 비교적 덜 까다롭게 구현할 수 있다.
  
  
• 2-2는 2-1의 단계에서 빈 칸을 찾지 못했을 경우에만 실행 되어야 한다.
  따라서 매 time마다 2-1에서 빈 칸을 찾았는지 못 찾았는지에 대해 체크해주어야 한다.
  나의 경우 can_spread로 체크한다.

 

---

소스코드

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct shark{
    int y, x, d, prior[4][4];

    void move(int ny, int nx, int dy) {
        y = ny, x = nx, d = dy;
    }
}shark;

const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, -1, 1 };

int n, m, k, pos[22][22];
int smell[22][22];
int owner[22][22];
vector <shark> sharks;

bool dead[404];
bool can_spread[404];

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    sharks.resize(m + 1);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &pos[i][j]);
            if (pos[i][j] > 0) {
                sharks[pos[i][j]].y = i;
                sharks[pos[i][j]].x = j;
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &sharks[i].d);
        --sharks[i].d;
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j < 4; ++j) {
            for (int k = 0; k < 4; ++k) {
                scanf("%d", &sharks[i].prior[j][k]);
                --sharks[i].prior[j][k];
            }
        }
    }

    int time = 0;
    while (time++ < 1000) {
        //1. 냄새 뿌리기
        for (int si = 1; si <= m; ++si) {
            if (dead[si]) continue;

            int sy = sharks[si].y;
            int sx = sharks[si].x;
            owner[sy][sx] = si;
            smell[sy][sx] = k;
        }

        //2. 냄새 없는 칸 찾기
        memset(can_spread, 0, sizeof(can_spread));
        for (int si = m; si >= 1; --si) {
            if (dead[si]) continue;

            int sy = sharks[si].y;
            int sx = sharks[si].x;
            int sd = sharks[si].d;
            
            for (int k = 0; k < 4; ++k) {
                int nd = sharks[si].prior[sd][k];
                int ny = sy + dy[nd];
                int nx = sx + dx[nd];

                if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                if (smell[ny][nx] == 0) {
                    dead[pos[ny][nx]] = true;
                    sharks[si].move(ny,nx,nd);
                    pos[sy][sx] = 0;
                    pos[ny][nx] = si;
                    can_spread[si] = true;
                    break;
                }
            }
        }

        for (int si = 1; si <= m; ++si) {
            if (dead[si] || can_spread[si]) continue;

            int sy = sharks[si].y;
            int sx = sharks[si].x;
            int sd = sharks[si].d;

            for (int k = 0; k < 4; ++k) {
                int nd = sharks[si].prior[sd][k];
                int ny = sy + dy[nd];
                int nx = sx + dx[nd];

                if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                if (owner[ny][nx] == si && smell[ny][nx] > 0) {
                    sharks[si].move(ny, nx, nd);
                    pos[sy][sx] = 0;
                    pos[ny][nx] = si;
                    break;
                }
            }
        }

        //4. 호르몬 1씩 줄여
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (smell[i][j] > 0)
                    smell[i][j]--;
            }
        }

        //1번 상어만 살았으면 종료
        bool fin = true;
        for (int i = 2; i <= m; ++i) {
            if (!dead[i]) {
                fin = false;
            }
        }
        if (fin) break;
    }
    if (time <= 1000) {
        printf("%d", time);
    }
    else {
        puts("-1");
    }
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 언제나 부드럽게 알려주세요.