백준 19273: 어른 상어

어른 상어 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

9595

3984

2398

38.665%

문제

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

<그림 1>

우선 순위상어 1상어 2상어 3상어 4↑↑↑↑↓↓↓↓←←←←→→→→

↓ ← ↑ →	↓ → ← ↑	→ ← ↓ ↑	← → ↑ ↓
→ ↑ ↓ ←	↓ ↑ ← →	↑ → ← ↓	← ↓ → ↑
← → ↓ ↑	← → ↑ ↓	↑ ← ↓ →	↑ → ↓ ←
→ ← ↑ ↓	→ ↑ ↓ ←	← ↓ ↑ →	↑ → ↓ ←

<표 1>

<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.

<그림 2>

<그림 3>

<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.

<그림 4>

<그림 5>

<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

예제 입력 1 복사

5 4 4
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3

예제 출력 1 복사

14

문제에 나온 그림과 같다.

예제 입력 2 복사

4 2 6
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2
4 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

예제 출력 2 복사

26

예제 입력 3 복사

5 4 1
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3

예제 출력 3 복사

-1

예제 입력 4 복사

5 4 10
0 0 0 0 3
0 0 0 0 0
1 2 0 0 0
0 0 0 0 4
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3

예제 출력 4 복사

-1

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 구현
• 시뮬레이션

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int dy[5] = { 0,-1,1,0,0 };//위 아래 
int dx[5] = { 0,0,0,-1,1 };//        왼 오
struct info {
    int x, y, dir;
    bool state = true;//상어 상태
};
struct SM {//냄세의 맵을 만들 자료구조
    int host, time;//냄세의 주인, 남은 시간
};
SM S_Map[20][20];//냄세지도
info shark[401];
int Map[20][20];//상어 지도
int priority[401][5][5];//상어의 갯수,방향,방향에따른 우선순위
int N, M, K;//격자크기, 상어 갯수, 냄세의 지속시간

int answer = 0;
void simul() {
    int cnt = 0;
    int SH = M;
    while (1) {
        if (SH == 1)break;
        if (cnt >= 1000) {
            answer = -1;
            return;
        }
        cnt++; answer++;
        //cout << answer << "단계";

        for (int i = 1; i <= M; i++) {
            if (shark[i].state == false)continue;
            int x = shark[i].x;
            int y = shark[i].y;
            int dir = shark[i].dir;
            int nx, ny, ndir;
            bool check = false;
            for (int k = 1; k <= 4; k++) {
                ndir = priority[i][dir][k];
                nx = x + dx[ndir];//다음 접점
                ny = y + dy[ndir];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N)continue;
                if (S_Map[ny][nx].host == 0) {
                    check = true;
                    shark[i].x = nx;
                    shark[i].y = ny;
                    shark[i].dir = ndir;
                    break;
                }
            }
            if (!check) {
                for (int k = 1; k <= 4; k++) {
                    ndir = priority[i][dir][k];
                    nx = x + dx[ndir];//다음 접점
                    ny = y + dy[ndir];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= N)continue;
                    if (S_Map[ny][nx].host == i) {
                        check = true;
                        shark[i].x = nx;
                        shark[i].y = ny;
                        shark[i].dir = ndir;
                        break;
                    }
                }
            }
        }
        memset(Map, 0, sizeof(Map));
        for (int i = 1; i <= M; i++) {
            if (shark[i].state == false)continue;

            int x = shark[i].x, y = shark[i].y;

            if (Map[y][x] == 0) {//상어가 없다
                Map[y][x] = i;
            }
            else {
                if (Map[y][x] < i) {
                    shark[i].state = false;
                    SH--;
                }
                else {
                    shark[Map[y][x]].state = false;
                    Map[y][x] = i;
                    SH--;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (Map[i][j] > 0) {
                    S_Map[i][j].host = Map[i][j];
                    S_Map[i][j].time = K;
                }
                else if (S_Map[i][j].time > 0) {
                    S_Map[i][j].time--;
                }
                if (S_Map[i][j].time == 0)
                    S_Map[i][j].host = 0;
            }
        }


    }

}

int main() {
    cin >> N >> M >> K;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int input; cin >> input;
            if (input > 0) {
                S_Map[i][j].host = input;
                S_Map[i][j].time = K;
                shark[input].y = i, shark[input].x = j;
            }
        }
    }
    for (int i = 1; i <= M; i++)
        cin >> shark[i].dir;

    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 4; k++) {
                int input; cin >> input;
                priority[i][j][k] = input;
            }
        }
    }
    simul();
    cout << answer;
    return 0;
}

 

음,,, 어려웠다 아침10시에 시작했는데, 지금 오후8시반이다;; 중간에 밥먹고 자고 그랬지만 이렇게 오래걸릴줄 몰랐다. 한 10시간반정도 풀었으면 다음 골드 2문제는 5시간을 목표로 해서 점점 줄여나가면 된다.!