미친 아두이노
문제 해석
- 종수의 아두이노 위치, 미친 아두이노 위치, 종수 아두이노의 움직임이 주어졌을 때, 모든 움직임이 끝난 후의 상태를 출력하는 문제입니다.
- 다음 5가지 과정이 반복됩니다.
- 종수의 아두이노를 주어진 움직임에 따라 움직이게 합니다.
- 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우 종료합니다.
- 미친 아두이노는 8방향 중, 종수의 아두이노와 가까워지는 방향으로 움직입니다.
- 미친 아두이노가 종수 아두이노의 위치에 도달하면 종료합니다.
- 2개 이상의 미친 아두이노가 같은 위치에 있으면, 해당 칸에 있는 아두이노들은 모두 폭파됩니다.
- 주어진 움직임이 끝나기 전에 종료되면 현재까지 움직인 횟수를 출력합니다.
설계(20)
- 구현문제로 미친 아두이노의 상태를 어떻게 표현할지 생각하는데 시간이 너무 오래걸렸습니다.
- 먼저 전체적으로 움직인 상태를 표현하기 위해서 adj(변수이름) 2차원 배열을 선언한 후, 각 좌표에 아두이노가 몇개 들어있는 지 카운트를 하였습니다.
- 해당 아두이노들의 좌표를 adj 2차원 배열에 카운트(이전좌표는 - , 현재 좌표는 +)하여, 종수의 아두이노 차례에서 2보다 크거나 같으면 종료하도록 하였습니다.
- 두번째로, 미친 아두이노가 움직일 때 이전 좌표를 알지 못하기 때문에 각 아두이노의 좌표를 저장하는 배열을 이용하였습니다.
- 마지막으로 미친 아두이노가 이동을 모두 마친 후, 2개 이상인 좌표를 찾는 부분을 2차원 벡터를 이용하려고 했으나, 스택메모리제한에 걸려서 사용을 하지 못했습니다.
- 대신에 map(stl)을 사용하였고 키는 <x,y좌표>, 변수는 벡터로 선언하였습니다. (해당 map은 main문 바깥에서 선언해서 스택메모리가 아닙니다.)
- 미친 아두이노의 이동을 모두 마친 후, map을 조사하여 해당 <x,y>좌표에 들어있는 벡터사이즈가 2 이상이면 해당 아두이노들의 좌표를 {-1,-1}처리하여 구분하도록 했습니다.
구현(120)
코드1
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#define MAXN 101
using namespace std;
char arr[MAXN][MAXN];
int N, M;
pair<int,int> prev_arr[MAXN * MAXN];
int idx = 0;
int sx, sy;
int adj[MAXN][MAXN];
int dx[] = { 1,1,1,0,0,0,-1,-1,-1 };
int dy[] = { -1,0,1,-1,0,1,-1,0,1 };
map<pair<int,int> ,vector<int> > mp;
pair<int, int> min_coord(int idx, int x, int y) {
pair<int, int> ans;
int dist = 2 * MAXN;
for (int i = 0; i < 9; i++) {
if (i == 4) continue;
int nx = prev_arr[idx].first + dx[i];
int ny = prev_arr[idx].second + dy[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
int next_dist = abs(nx - x) + abs(ny - y);
if (next_dist < dist) {
dist = next_dist;
ans = { nx,ny };
}
}
return ans;
}
int main() {
//freopen("roboti.in.8", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> arr[i][j];
if (arr[i][j] == 'R') {
prev_arr[idx++] = { i,j };
adj[i][j]++;
arr[i][j] = '.';
}
else if (arr[i][j] == 'I') {
sx = i, sy = j;
adj[i][j]++;
arr[i][j] = '.';
}
}
}
string s;
cin >> s;
int ans = 0;
int i;
for (i = 0; i < s.length(); i++) {
mp.clear();
int order = (s[i] - '0') - 1;
adj[sx][sy]--;
sx += dx[order];
sy += dy[order];
adj[sx][sy]++;
if (adj[sx][sy] >= 2) {
cout << "kraj " << i+1 << "\n";
return 0;
}
for (int j = 0; j < idx; j++) {
if (prev_arr[j].first == -1) continue;
pair<int,int> coord = min_coord(j, sx, sy);
adj[prev_arr[j].first][prev_arr[j].second]--;
prev_arr[j] = coord;
adj[prev_arr[j].first][prev_arr[j].second]++;
mp[prev_arr[j]].push_back(j);
}
for (auto it = mp.begin(); it != mp.end(); it++) {
pair<int, int> coord = (*it).first;
if (coord.first == sx && coord.second == sy) {
cout << "kraj " << i + 1 << "\n";
return 0;
}
vector<int> tmp_v = (*it).second;
if (tmp_v.size() >= 2) {
adj[coord.first][coord.second] = 0;
for (int k = 0; k < tmp_v.size(); k++) {
prev_arr[tmp_v[k]] = { -1,-1 };
}
}
}
}
for (int i = 0; i < idx; i++) {
if (prev_arr[i].first == -1) continue;
int x = prev_arr[i].first;
int y = prev_arr[i].second;
arr[x][y] = 'R';
}
arr[sx][sy] = 'I';
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << arr[i][j];
}
cout << "\n";
}
코드 2(대회에서 제공하는 솔루션)
- 대회에서 제공한 솔루션을 보면 제가 생각했던 방법들이 허무할 정도로 간단하게 구현을 한 것을 볼 수 있습니다..
- 다음 이동에서 두개 이상의 아두이노가 만나는 부분을 X로 변환시키는 방법을 이용해서 간단하게 구현이 되었습니다.
#include <cstdio>
#include <cstring>
#define MAXR 100
#define MAXS 100
#define MAXPOTEZA 100
int R, S, N;
char ploca[MAXR][MAXS+1], pomocna[MAXR][MAXS+1];
char igrac[MAXPOTEZA+1];
int sgn( int x ) {
if( x < 0 ) return -1;
if( x > 0 ) return 1;
return 0;
}
int main( void ) {
int R, S;
scanf( "%d%d", &R, &S );
for( int r = 0; r < R; ++r ) scanf( "%s", ploca[r] );
scanf( "%s", igrac );
N = strlen( igrac );
int igrac_r, igrac_s;
for( int r = 0; r < R; ++r )
for( int s = 0; s < S; ++s )
if( ploca[r][s] == 'I' ) {
igrac_r = r;
igrac_s = s;
}
for( int i = 0; i < N; ++i ) {
for( int r = 0; r < R; ++r )
for( int s = 0; s < S; ++s )
pomocna[r][s] = '.';
igrac_r += 1 - (igrac[i]-'1')/3;
igrac_s += (igrac[i]-'1')%3 - 1;
if( ploca[igrac_r][igrac_s] == 'R' ) {
printf( "kraj %d\n", i+1 );
return 0;
}
pomocna[igrac_r][igrac_s] = 'I';
for( int r = 0; r < R; ++r )
for( int s = 0; s < S; ++s )
if( ploca[r][s] == 'R' ) {
int dr = sgn( igrac_r - r );
int ds = sgn( igrac_s - s );
if( pomocna[r+dr][s+ds] == 'I' ) {
printf( "kraj %d\n", i+1 );
return 0;
}
if( pomocna[r+dr][s+ds] == '.' ) pomocna[r+dr][s+ds] = 'R';
else pomocna[r+dr][s+ds] = 'X';
}
for( int r = 0; r < R; ++r )
for( int s = 0; s < S; ++s ) {
if( pomocna[r][s] == 'X' ) pomocna[r][s] = '.';
ploca[r][s] = pomocna[r][s];
}
}
for( int r = 0; r < R; ++r ) printf( "%s\n", ploca[r] );
return 0;
}
디버깅
- 시간이 아주 오래걸린 이유중 하나는 위 설계에서 말한 마지막 작업을 생각하는데 오래걸렸고, 두번째로 미친 아두이노의 개수가 2개이상인 좌표의 adj값을 0으로 초기화해주지 않았기 때문입니다.
제출결과
- 56ms
마무리
- 쉬운 방법을 생각치 못하고 어렵게 돌아간 듯한 문제입니다. 덕분에 시간이 너무 오래걸려서 풀었다고 하기에는 민망할 정도입니다. 무조건 다시 풀어봐야할 문제인 것 같습니다.