[백준] 17780번 새로운 게임

17780 새로운 게임

문제) https://www.acmicpc.net/problem/17780

풀이)

시뮬레이션 문제이다.

선언한 자료들

① 말의 정보를 저장하는 구조체를 선언 & 정보 저장 배열 선언

struct horse {

int y, x, dir; // 말의 위치, 방향 

};

vector<horse> h_info;

② 체스판의 상태를 나타내는 int map[12][12]; 선언

③ 체스판의 위치에서, 가장 아래쪽에 있는 말 번호를 저장하는 int horse_map[12][12]; 선언

만약 (1,1) 자리에 1 - 3 - 4번 순으로 말들이 쌓여있다면

horse_map[1][1] = 1이다.

④ 각 말들이 업고? 있는 말 정보 저장하는 vector<int> parent[10]; 선언

만약 1 - 3 - 4 순으로 말들이 쌓여있다면 -> 1번 말이 3번과 4번말을 업고 있다고 생각

parent[1] = {1,3,4};

parent[3]  empty

parent[4]  empty 이다.

위의 선언한 것들을 이용한 과정은 아래와 같다.

1. 체스판의 상태와 말의 위치와 방향 입력받음

2. 0번째 말부터 K-1번째 말 이동 시작(만약 i번째 말이 다른 말에게 업혀있는 상태(parent[i] empty)라면 pass)

  2.1 말이 이동할 위치가 흰색 칸일경우 : 그대로 이동. 

  2.2 말이 이동할 위치가 빨간색 칸일 경우 : 만약 여러 말들을 업고 있었다면 순서를 바꿔준 뒤 이동. 

  2.3 말이 이동할 위치가 map범위를 벗어나거나 파란색 칸일 경우 : 방향을 먼저 바꿈.

  바꾼 방향으로 이동할 위치 다시 확인

  그 위치가 흰색 칸이거나 빨간색 칸일 경우에만 이동.

3. 각 말들이 업고있는 개수를 확인해 그 개수가 4이상이라면 횟수 출력

   (parent[i] >= 4?)

   4개 이상이 없다면 다시 2번으로 돌아감.

+) 설명하기 어렵다.

    한 줄씩 디버깅하면서 본다면 이해하기 쉬울 것이다.

코드)

#include<stdio.h>
#include<vector>
using namespace std;
 
struct horse {
    int y, x, dir;
    horse() {
        y = -1;
        x = -1;
        dir = 0;
    }
    horse(int y, int x, int dir) {
        this->y = y;
        this->x = x;
        this->dir = dir;
    }
};
 
int N, K;
int result = -1;
int map[12][12];
int horse_map[12][12];
vector<int> parent[10];
vector<horse> h_info;
bool suc = false;
//방향 오른쪽 1 왼쪽 2 위쪽 3 아래쪽 4
int dy[5] = { 0,0,0,-1,1 };
int dx[5] = { 0,1,-1,0,0 };
 
void move(int i) {
    int ny = h_info[i].y + dy[h_info[i].dir];
    int nx = h_info[i].x + dx[h_info[i].dir];
 
    //범위밖, 파란색 칸 : 방향 반대로 바꾸고 한칸이동
    if (ny < 0 || ny >= N || nx < 0 || nx >= N || map[ny][nx] == 2) {
        //방향 바꿈
        if (h_info[i].dir % 2 == 0) {
            h_info[i].dir -= 1;
        }
        else {
            h_info[i].dir += 1;
        }
        //바뀐 방향으로 이동할 칸 확인
        ny = h_info[i].y + dy[h_info[i].dir];
        nx = h_info[i].x + dx[h_info[i].dir];
        
        //방향을 반대로 한 후 이동하려는 칸이 파란색 또는 범위 밖을 벗어나는 곳이라면
        //방향만 바꿈.
        if (ny < 0 || ny >= N || nx < 0 || nx >= N || map[ny][nx] == 2) return;
        
        //흰색칸 혹은 빨간칸일 경우 그 칸으로 이동
        move(i);
    }
    else if (map[ny][nx] == 0) {//흰색칸
    
        horse_map[h_info[i].y][h_info[i].x] = -1;//원래있던 칸 초기화 하고 이동
        for (int t = 0; t < parent[i].size(); t++) {//i번째 말이 업고 있는 말들의 위치도 바꿔줌
            h_info[parent[i][t]].y = ny;
            h_info[parent[i][t]].x = nx;
        }
        
        if (horse_map[ny][nx] != -1) {//이동할 칸에 누가 있다면
            for (int t = 0; t < parent[i].size(); t++) { //그 칸에 있는 말에게 다 업힘, 맨 위에 삽입
                parent[horse_map[ny][nx]].push_back(parent[i][t]);
            }
 
            parent[i].clear();//새로운 칸의 말에게 모두 업혔으므로 초기화
        }
        else {//이동할 칸에 누가 없었다면, 그 칸의 주인이 됨
            horse_map[ny][nx] = i;
        }
    }
    else if (map[ny][nx] == 1) {//빨간색칸
 
        horse_map[h_info[i].y][h_info[i].x] = -1;
        for (int t = 0; t < parent[i].size(); t++) {
            h_info[parent[i][t]].y = ny;
            h_info[parent[i][t]].x = nx;
        }
        
        int new_leader = parent[i].back(); //맨 위에 업혀 있던 말이 맨 아래로 오게됨 
        if (new_leader != i) {//i번째 말이 다른 말들을 업고 있었다면 순서 뒤바꿈
            for (int t = parent[i].size() - 1; t >= 0; t--) {
                parent[new_leader].push_back(parent[i][t]);
            }
            parent[i].clear();
        }
        
        if (horse_map[ny][nx] != -1) {//이동할 칸에 누가 있다면
            for (int t = 0; t < parent[new_leader].size(); t++) {
                parent[horse_map[ny][nx]].push_back(parent[new_leader][t]);
            }
            parent[new_leader].clear();
        }
        else {
            horse_map[ny][nx] = new_leader;
        }
 
    }
 
}
int main() {
    scanf("%d %d", &N, &K);
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
            horse_map[i][j] = -1;
        } 
    }
    for (int i = 0; i < K; i++) {
        int y, x, dir;
        scanf("%d %d %d", &y, &x, &dir);
        horse_map[y-1][x-1] = i;
        h_info.push_back({ y-1,x-1,dir });
        parent[i].push_back(i);
    }
    int cnt = 1;
    
    while (cnt <= 1000 && suc == false)
    {
        //0번말부터 이동
        for (int i = 0; i < K; i++) {
            if (parent[i].empty()) continue;
            move(i);
        }
        for (int i = 0; i < K; i++) {
            if (parent[i].size() >= 4) {
                suc = true;
                result = cnt;
                break;
            }
        }
        cnt++;
    }
    printf("%d", result);
    return 0;
}