[백준] 8972 - 미친 아두이노

1. 문제 이해

2차원 배열 위에 종수의 아두이노 1개와 미친 아두이노 여러개가 있다. 2차원 배열 위에서 게임을 한다. 5가지 과정이 반복된다고 하는데, 3가지 과정으로 요약할 수 있다.

 

1. 종수의 아두이노가 이동한다. 이 때 이동위치에 미친 아두이노가 있는지 체크한다. 
2. 미친 아두이노들을 종수의 아두이노에 가깝게 한 칸 이동시킨다. 이 때, 종수한테 이동했는지 체크한다.
3. 미친 아두이노들이 한 위치에 여러개 있는지 체크한다.

 

 1번과 2번 과정의 경우, 게임을 바로 종료시킬 수 있다. 3번 과정의 경우 미친 아두이노들의 수를 줄일 수 있다. 2차원 배열의 범위가 가로, 세로 각각 100 이하이므로 간단한 구현문제로 생각할 수 있다.

 

문제에 따로 설명은 없지만, 미친 아두이노들이 순서대로 혹은 동시에 이동하는 지 확실하게 정해야 한다. 언급이 없었고 2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우 라는 묘사가 있었으므로동시에 이동하는 것으로 판단했다.

 

---

2. 문제 풀이

위에 표시된 3가지 과정을 각각 함수로 작성해 문제를 푼다. 여기서 주의해야 할 점은 아두이노들을 동시에 이동시키는 것이다. 순차적으로 미친 아두이노들을 이동시키는 것과 동시에 미친 아두이노들을 이동시키는 것은 결과가 다르기 때문이다.

 

 순차적으로 이동시킬 경우, 미친 아두이노들이 한 칸에 2개 초과 있을 수 없다. 미친 아두이노들이 한 칸에 3개 있다고 가정하면 마지막으로 들어온 미친 아두이노는 제거되지 않는다. 큐를 이용해 구현하는 방법도 있지만 복잡하므로 간단한 방법을 선택했다.

 

 미친 아두이노들을 2차원 배열과 1차원 배열에 저장시킨다. 2차원 배열은 출력을 위한 용도이므로 미친 아두이노들 끼리 구분이 되지않아도 상관없다. 1차원 배열에는 인덱스를 번호로 하는 미친 아두이노들의 위치 좌표가 저장된다. 

 

 미친 아두이노들을 이동시키면 2차원 배열에서는 임시로 삭제하고, 1차원 배열의 위치 좌표만 변경한다. 이 때, 중복 여부를 체크하기 위해 또다른 2차원 배열을 만든다. 그리고 추가로 Bool 형 1차원 배열을 만들어 어떤 번호의 미친 아두이노가 겹치는지 확인한다. 이 때, 미친 아두이노의 이동 좌표가 종수의 아두이노 좌표와 겹친다면 바로 종료시킨다.

 

// 자리 비워주고
board[crazy_arduino[i].y][crazy_arduino[i].x] = '.';
crazy_arduino[i].y = dy; // i번 아두이노의 이동 좌표
crazy_arduino[i].x = dx; // i번 아두이노의 이동 좌표

// 아두이노 번호 넣는다.
if(copy[dy][dx] == -1) {
	copy[dy][dx] = i;
} else {
	// 아두이노 삭제 예약
	delete_arduino[i] = true;
	delete_arduino[copy[dy][dx]] = true;
}

 board는 입력으로 받은 2차원 배열이고, copy는 어떤 아두이노들이 겹치는지 빠르기 확인하기 위한 2차원 배열이다.

crazy_arduino라는 배열에는 미친 아두이노들의 위치 좌표가 저장되어 있다. 

 copy 배열을 -1로 초기화 하고,  미친 아두이노들의 이동 좌표에 해당되는 곳에 아두이노의 번호를 저장시킨다. 만약 -1이 아니라면, 즉 겹치는 경우라면 delete_arduino 라는 boolean 배열에 체크를 한다.

 

이렇게 하면 아두이노들이 겹치는지 체크하고, 지우는데 걸리는 시간이 O(미친아두이노 수) 임이 항상 보장된다. 

 

미친 아두이노들의 이동 방향을 찾는 것은 간단하다. 문제에 나와있는 대로만 하면 방향을 구할 수 있다. 이 때, 배열의 인덱스와 방향 번호를 일치시켜 주면 코드가 깔끔해진다.

 

int dir[10][2] = {{0,0}, {1,-1}, {1,0}, {1,1}, {0,-1}, {0,0}, {0,1}, {-1,-1}, {-1,0}, {-1,1}};
// 방향 찾는다
int dir_type = -1;
int minDist = 987654321;
for(int j=1; j<=9; j++) {
	int dy = crazy_arduino[i].y + dir[j][0];
	int dx = crazy_arduino[i].x + dir[j][1];
	int tmpDist = abs(dy - jongsu_point.y) + abs(dx - jongsu_point.x);
	if(tmpDist <= minDist ) {
		minDist = tmpDist;
		dir_type = j;
     }
}
// dir_type이 미친 아두이노의 이동 방향이 된다.

---

3. 제출 결과

---

4. 문제 코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <string.h>

#define y first
#define x second

int dir[10][2] = {{0,0}, {1,-1}, {1,0}, {1,1}, {0,-1}, {0,0}, {0,1}, {-1,-1}, {-1,0}, {-1,1}};
using namespace std;
char board[111][111];
vector<pair<int,int>> crazy_arduino;
pair<int,int> jongsu_point;
bool delete_arduino[10011];
int R, C; 
bool moveJongsu(int dir_type) {
    
    int dy = jongsu_point.y + dir[dir_type][0];
    int dx = jongsu_point.x + dir[dir_type][1];

    if(dy <0 || dx < 0 || dy >= R || dx >= C) { return true; } 

    if(dy == jongsu_point.y && dx == jongsu_point.x) {
        return true;
    } 

    if(board[dy][dx] == '.') {
        board[jongsu_point.y][jongsu_point.x] = '.';
        board[dy][dx] = 'I';
        jongsu_point = {dy, dx};
        return true;
    } else {
        return false;
    }
}

bool moveCrazyArduino() {
    int size = crazy_arduino.size();
    int copy[111][111]; 
    memset(copy, -1, sizeof(copy));
    memset(delete_arduino, 0, sizeof(delete_arduino));

    for(int i=0; i<size; i++) {
        if(crazy_arduino[i].y == -1) { continue; }

        int dir_type = -1;
        int minDist = 987654321;
        for(int j=1; j<=9; j++) {
            int dy = crazy_arduino[i].y + dir[j][0];
            int dx = crazy_arduino[i].x + dir[j][1];
            int tmpDist = abs(dy - jongsu_point.y) + abs(dx - jongsu_point.x);
            if(tmpDist <= minDist ) {
                minDist = tmpDist;
                dir_type = j;
            }
        }

        int dy = crazy_arduino[i].y + dir[dir_type][0];
        int dx = crazy_arduino[i].x + dir[dir_type][1];
        
        if(dy < 0 || dx < 0 || dy >= R || dx >= C) { continue; }

        if(board[dy][dx] == 'I') { return false;}

        board[crazy_arduino[i].y][crazy_arduino[i].x] = '.';
        crazy_arduino[i].y = dy;
        crazy_arduino[i].x = dx;
        if(copy[dy][dx] == -1) {
            copy[dy][dx] = i;
        } else {
            delete_arduino[i] = true;
            delete_arduino[copy[dy][dx]] = true;
        }
    }
    return true;
}

void checkCrazyArduino() {
    int size = crazy_arduino.size();
    for(int i=0; i<size; i++) {
        if(delete_arduino[i]) {
            crazy_arduino[i].y = -1;
            crazy_arduino[i].x = -1;
        }
    }

    for(int i=0; i<size; i++) {
        if(crazy_arduino[i].y != -1) {
            board[crazy_arduino[i].y][crazy_arduino[i].x] = 'R';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> R >> C;
    for(int i=0; i<R; i++) {
        cin >> board[i];
        for(int j=0; j<C; j++) {
            if(board[i][j] == 'I') {
                jongsu_point = {i, j};
            } else if (board[i][j] == 'R') {
                crazy_arduino.push_back({i,j});
            }
        }
    }

    string s; cin >> s;
    int len = s.length();
    int status = -1;
    for(int i=0; i <len; i++) {
        if(!moveJongsu(s[i] - '0')) {
            status = i+1;
            break;
        }
        if(!moveCrazyArduino()) {
            status = i+1;
            break;
        } else {
            checkCrazyArduino();
        }
    }

    if(status != -1) {
        cout << "kraj " << status;
    } else {
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                cout << board[i][j];
            } cout << "\n";
        }
    }
}