[백준 17837번 새로운 게임 2] - C++

statco19·2022년 1월 31일
0

알고리즘연습

목록 보기
20/27

[백준 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;
}

실행 결과

profile
조금씩 나아지는 중입니다!

0개의 댓글