[백준 17837번 새로운 게임 2]
https://www.acmicpc.net/problem/17837
별다른 알고리즘이 없는 구현 문제였다. C++의 메모리 문법이 익숙치 않아 디버깅에 꽤나 오랜 시간이 소모되었다. 더 많은 경험을 통해 참조자 문법에 익숙해져 나가야 할 것 같다.
풀이
1.
말의 이동 방법이 크게 세 가지다. 흰 칸, 빨간 칸, 파란 칸(범위를 벗어나는 것 포함)으로 나누어진다.
빨간 칸의 경우 우선 흰 칸처럼 말을 움직이고 말이 쌓여있는 순서를 뒤바꾸는 로직이 추가된다.
필자는 흰 칸으로 가는 움직임을 메서드로 구현했고, 빨간 칸으로 가는 메서드는 흰 칸으로 가는 메서드를 활용해서 구현했다. 파란 칸으로 가는 메서드 내에서도 방향을 바꿔 흰 칸 혹은 빨간 칸으로 갈 수 있기 때문에, 결과적으로 흰 칸으로 가는 메서드를 잘 구현하는 게 중요했다.
2.
흰 칸의 경우 현재 움직이는 말이 몇 번째 말인지 확인한 후, 해당 번호의 말 위에 다른 말이 쌓여있으면 같이 움직여주는 로직을 구현하였다. 이 과정에서 참조자로 받은 r의 값이 계속 변경되는 걸 발견하지 못하여 오랜 시간 동안 디버깅을 하였다.
3.
빨간 칸의 경우 흰 칸 메서드를 활용하고, <algorithm> 헤더 파일에 존재하는 reverse 메서드를 사용하여 순서가 바뀌어야 하는 부분을 골라 순서를 뒤바꿔 주었다.
4.
파란 칸의 경우, 방향 전환 후 범위를 벗어나거나 파란 칸인 경우, (0,0)을 반환하여 무한 루프를 멈춰주었고, 그 이외에는 해당 칸이 흰 색인지 빨간 색인지에 따라 알맞는 메서드를 호출하였다.
C++ 코드
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility> // pair
#include <tuple>
#include <stack>
// #include <map>
#include <unordered_map>
#define ll long long
#define INF 1e9
using namespace std;
int ans = 0;
int n,k;
vector<int> bd[13][13];
int map[13][13];
vector<vector<int> > pieces;
int dr[] = {0,0,0,-1,1};
int dc[] = {0,1,-1,0,0};
bool gameOver = false;
pair<int,int> white(int& r, int& c, int& d, int seq) {
int nr,nc;
nr = r+dr[d];
nc = c+dc[d];
vector<int>& v = bd[r][c];
auto it = find(v.begin(), v.end(), seq);
int idx = it-v.begin();
vector<int> moving;
int size = v.size();
for(int i=idx;i<size;++i) {
int s = v[i];
pieces[s-1][0] = nr; // int &r is changed
pieces[s-1][1] = nc; // int &c is changed
moving.push_back(s); // moving seqs
}
for(int i=size-1;i>=idx;--i) {
v.pop_back();
}
v.resize(idx);
for(int i=0;i<moving.size();++i) {
bd[nr][nc].push_back(moving[i]);
}
return make_pair(nr,nc);
}
pair<int,int> red(int& r, int& c, int& d, int seq) {
int nr = r+dr[d];
int nc = c+dc[d];
white(r,c,d,seq);
vector<int>& v = bd[nr][nc];
auto it = find(v.begin(), v.end(), seq);
int idx = it-v.begin();
reverse(v.begin()+idx, v.end());
return make_pair(nr,nc);
}
pair<int,int> blue(int& r, int& c, int& d, int seq) {
if(d==1) {d=2;}
else if(d==2) {d=1;}
else if(d==3) {d=4;}
else if(d==4) {d=3;}
int nr = r+dr[d];
int nc = c+dc[d];
if(!(1<=nr&&nr<=n && 1<=nc&&nc<=n) || (map[nr][nc]==2)) {
return make_pair(0,0); // out of bound
} else {
if(map[nr][nc] == 0) {
white(r,c,d,seq);
} else if(map[nr][nc] == 1) {
red(r,c,d,seq);
}
}
return make_pair(nr,nc);
}
void sol() {
ans++;
for(int k=0;k<pieces.size();++k) { // pieces.size()
int seq = k+1;
int &r = pieces[k][0];
int &c = pieces[k][1];
int &d = pieces[k][2];
int nr,nc;
nr = r+dr[d];
nc = c+dc[d];
pair<int,int> p;
// out of bound (blue) 2
if(!(1<=nr&&nr<=n && 1<=nc&&nc<=n)) {
p = blue(r,c,d,seq);
}
// white 0
else if(map[nr][nc] == 0) {
p = white(r,c,d,seq);
}
// red 1
else if(map[nr][nc] == 1) {
p = red(r,c,d,seq);
}
// blue 2
else if(map[nr][nc] == 2) {
p = blue(r,c,d,seq);
}
int a,b;
a = p.first;
b = p.second;
if(a==0 && b==0) { // out of bound
continue;
} else {
if(bd[a][b].size() >= 4) {
gameOver = true;
break;
}
}
}
return;
}
int main(void) {
// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
scanf("%d%d", &n, &k);
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
scanf("%d", &map[i][j]);
}
}
for(int i=0;i<k;++i) {
int r,c,d;
scanf("%d%d%d", &r,&c,&d);
vector<int> v;
v.push_back(r); v.push_back(c); v.push_back(d);
pieces.push_back(v);
bd[r][c].push_back(i+1);
}
while(ans <= 1000) {
sol();
if(gameOver) break;
}
if(ans > 1000) {
ans = -1;
}
printf("%d\n", ans);
return 0;
}실행 결과
