[백준] 어른 상어 19237번 (c++) 구현

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

 

풀이 방법

호흡이 긴 문제 이므로 구현해야 할 것을 정리하자 

 

• 턴마다 수행해야 할 것
  • 상어 이동
    • 방향 정하기
    • 겹치면 강한 상어 살아남기
  • 냄새 시간 제거
    • 시간 0이면 냄새 제거
  • 냄새 생성

위와 같이 순서를 정할 수 있다. 이제 구현할 때 사용할 자료구조를 선택하자

일단 저장해야 할 자료 : 상어의 위치, 냄새 (시간, 위치, 누구의 냄새인지)를 저장해야 한다.

이를 위해 상어의 위치는 pair<int, int>의 벡터로 저장했다. 

또한 냄새도 매 턴이 지날 때마다, 시간을 1씩 감소해야 하므로 2차원 배열을 사용하기보단, vector<pair<pair<int, int>, int>를 활용하여 저장했다.

냄새를 따로 저장했고, 상어의 이동을 위해 해당 상어의 상하좌우에 어떤 상어의 냄새가 있는지 빠르게 판단하기 위해 sea[21][21] 배열을 활용하여, 냄새의 주인을 저장했고, 냄새의 시간이 0이 된다면 sea배열을 0으로 다시 초기화했다.

상어의 움직임은 번호가 낮은 상어부터 움직였다. 

또한 해당 칸에 상어가 존재하는지 판단하기 위해 visited 배열을 사용했는데 이는 상어가 동시에 겹칠 때, 번호가 낮은 상어가 먼저 이동했으므로, 해당 칸은 visited 되어 있고 이후, 번호가 높은 상어가 방문하기 때문에 이 경우에 해당하면 뒤늦게 방문한 상어를 제거했다.

상어가 제거된 경우 y, x좌표를 -1로 설정해 구분했다.

그리고 flag를 사용해 상하좌우에 빈칸이 있으면, true로 만들어 주고 없으면 자신의 냄새가 존재하는 칸을 저장을 통해 해당 칸으로 이동하게 했다.

 

상어마다 다른 이동 우선순위를 설정해 주기 위해 shark_pri배열을 현재 방향을 고려해 선언해서 저장해 두고 사용했다.

 

냄새의 시간을 줄이기 위해, 매번 new_smell_loc을 선언하고 시간이 0이 되지 않거나 해당 위치에 상어가 존재하지 않는 경우만 push_back을 하여 smell_loc을 update 해 주었다. 만약 상어가 존재하는 경우라면 빈 공간이 없어 상어가 자신의 냄새 방향으로 온 경우이므로 기존 냄새는 제거하고 다시 K를 추가하면 되기 때문에, 추가하지 않았다.

 

#include<iostream>
#include<vector>
#include<memory.h>

using namespace std;

// 1, 2, 3, 4 = 위, 아래, 왼 쪽, 오른 쪽

int N, M, K, live_shark; //격자, 상수 수, 냄새 시간
int sea[21][21]; // 어떤 상어의 냄새인지 저장하기
int visited[21][21]; // 상어의 존재 여부 관리, 현재 상어가 존해 하냐
int shark_dir[402];
int shark_pri[402][4][4]; // 상어 우선순위
vector<pair<pair<int, int>, int> > smell_loc; // y, x, time
pair<int, int> shark_loc[402];
int dy[4] = { -1, 1, 0, 0 }; // 위. 아래, 왼, 오
int dx[4] = { 0, 0, -1, 1 };

void Input() {
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < N; i++) { // 현재 바다,
        for (int j = 0; j < N; j++) {
            int temp;
            cin >> temp;
            sea[i][j] = temp;
            if (temp > 0) {
                smell_loc.push_back(make_pair(make_pair(i, j), K));
                shark_loc[temp] = make_pair(i, j);
                visited[i][j] = 1;
            }
        }
    }

    for (int i = 1; i < M + 1; i++) { // 상어의 현재 방향
        int dir;
        cin >> dir;
        shark_dir[i] = dir - 1;
    }

    for (int i = 1; i < M + 1; i++) { // 우선순위를 입력 받는다.        
        for (int j = 0; j < 4; j++) {
            for (int z = 0; z < 4; z++) {
                int dir;
                cin >> dir;
                shark_pri[i][j][z] = dir - 1;
            }
        }
    }

    return;
}

void move_shark() {
    for (int i = 1; i < M + 1; i++) { // 상어 번호
        // 빈 곳 찾기
        int y = shark_loc[i].first;
        int x = shark_loc[i].second;        
        if (y == -1 || x == -1) continue; // 상어 사망한 경우
        bool flag = false; // 빈 칸이 있는 경우 true, 없으면 false;
        pair<pair<int, int>, int> is_smell_loc = make_pair(make_pair(-1, -1), -1); // y, x, 방향
        for (int j = 0; j < 4; j++) {
            int next_dir = shark_pri[i][shark_dir[i]][j];
            int ny = y + dy[next_dir];
            int nx = x + dx[next_dir];
            if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
            if (sea[ny][nx] == 0) { // 냄새가 없는 경우
                flag = true; // 빈 곳이 있음
                if (visited[ny][nx] == 0) { // 상어 이동, 상어의 방향도 바꿔야함
                    visited[ny][nx] = 1;
                    visited[y][x] = 0;
                    shark_loc[i].first = ny;
                    shark_loc[i].second = nx;
                    shark_dir[i] = next_dir;
                    break;
                }
                if (visited[ny][nx] == 1) { // 상어 사망, 우선순위가 높은 상어가 먼저 위치해 있다.
                    visited[y][x] = 0;
                    shark_loc[i].first = -1;
                    shark_loc[i].second = -1;
                    live_shark--;
                    break;
                }
            }            
            if (sea[ny][nx] == i) { //자신의 냄새인 경우 일단 저장
                if (is_smell_loc.first.first == -1) {
                    is_smell_loc.first.first = ny; 
                    is_smell_loc.first.second = nx;
                    is_smell_loc.second = next_dir; // 다음 방향
                }
            }
        }
        if (!flag) { //자신의 냄새가 있는 곳으로 이동, 빈 곳이 없음
            shark_loc[i].first = is_smell_loc.first.first;
            shark_loc[i].second = is_smell_loc.first.second;
            visited[y][x] = 0;
            visited[shark_loc[i].first][shark_loc[i].second] = 1;
            shark_dir[i] = is_smell_loc.second;
        }
    }
}

void minus_smell() {
    vector<pair<pair<int, int>, int> > new_smell_loc;

    for (int i = 0; i < smell_loc.size(); i++) {
        int y = smell_loc[i].first.first;
        int x = smell_loc[i].first.second;
        smell_loc[i].second--; // 시간 감소
        if (visited[y][x] == 1) { // 상어가 있는 경우, 자시의 냄새로 온 경우 이므로, make_smell로 시간을 초기화
            continue;
        }
        if (smell_loc[i].second == 0) { // 냄새 사라짐
            sea[y][x] = 0; // 맵에 초기화
            continue;
        }
        // 냄새의 시간이 0이 아니고, 상어가 없는 경우만 다음 냄새에 추가해 준다.
        new_smell_loc.push_back(smell_loc[i]);
    }

    smell_loc = new_smell_loc; // smell 업데이트
}

void make_smell() {
    // 냄새가 있는 곳에 다시 가도 냄새를 다시 리필한다.
    for (int i = 1; i < M + 1; i++) {
        if (shark_loc[i].first == -1 || shark_loc[i].second == -1) { // 상어가 죽은 경우
            continue;
        }
        int ny = shark_loc[i].first;
        int nx = shark_loc[i].second;
        sea[ny][nx] = i;
        smell_loc.push_back(make_pair(make_pair(ny, nx), K));
    }
}

void turn() {
    int time = 0;
    while (live_shark != 1) {
        if (time >= 1000) {
            cout << -1 << '\n';
            return;
        }
        move_shark();
        minus_smell();
        make_smell();
        time++;
    }
    cout << time << '\n';
}
int main() {

    cin >> N >> M >> K;
    live_shark = M;
    Input();
    turn();

    return 0;
}