BOJ 17837

31 Jan 2020 • ProblemSolving

새로운게임 2

문제출처

문제 해석

  • 체스판의 말을 움직여서 쌓인 말의 개수가 4개 이상이 되기 위한 시간을 출력하는 문제입니다.

  • 말들을 모두 움직이는데 이동하려는 칸에 따라 다음과 같이 변화합니다.

    1. 이동하려는 칸이 흰색인 경우

      해당 말 위에 있는 모든 말을과 같이 다음 칸으로 이동합니다. 이동하려는 칸에 말이 쌓여있는 경우, 그대로 이어서 쌓으면 됩니다.

    2. 빨간색인 경우

      흰색과 같이 이동하고, 말이 쌓인 순서를 반대로 바꿉니다.

    3. 파란색 or 범위를 벗어나는 경우

      이동방향을 반대로 하고 이동하였을 때, 그 칸 또한 파란색 or 범위를 벗어나면 방향만 바꾸고 이동하지 않습니다.
      위의 경우가 아니면 a,b 조건으로 이동합니다.

설계(20)

  • 각 말의 위치(x,y)와 이동방향을 기록하는 1차원 배열을 두고, 각 말이 이동할 때마다 위치와 방향을 갱신시켜줍니다.
  • 2차원 벡터를 통해 말을 쌓을 수 있게 합니다.
  • 이동할 칸이 파란색이거나 범위가 벗어나는 경우를 우선적으로 검사해서 이동방향을 바꿔준 후, 한번더 조사를 했을 시 위와 같은 조건에 또 걸리게 되면 진행하지 않도록 합니다.
  • 이동시간(T) <= 1000 이므로, O(T*(K^2))의 시간복잡도로 그냥 구현을 해도 테스트를 통과하기에 충분한 시간입니다.

구현(60)

코드
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 12

struct node {
	int x;
	int y;
	int dir;
};
node horse[10];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };

vector<int> map[MAXN][MAXN];
int arr[MAXN][MAXN];
int N, K;
bool is_range(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= N) return false;
	return true;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int ans = 0;
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < K; i++) {
		int x, y, dir;
		cin >> x >> y >> dir;
		x--;
		y--;
		dir--;
		horse[i] = { x,y,dir };
		map[x][y].push_back(i);
	}
	while (ans <= 1000) {
		ans++;
		for (int i = 0; i < K; i++) {
			int x = horse[i].x;
			int y = horse[i].y;
			int dir = horse[i].dir;
			int start;
			for (start = 0; start < map[x][y].size(); start++) {
				if (map[x][y][start] == i) break;
			}
			
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (!is_range(nx, ny) || arr[nx][ny] == 2) {
				if (dir <= 1) {
					dir = 1 - dir;
				}
				else {
					dir = (3 - dir) + 2;
				}
				horse[i] = { x,y,dir };
				nx = x + dx[dir];
				ny = y + dy[dir];
			}
			if (!is_range(nx, ny) || arr[nx][ny] == 2) {
				horse[i] = { x,y,dir };
				continue;
			}
			// 이동할 칸이 흰색인 경우
			if (arr[nx][ny] == 0) {
				int num = map[x][y].size() - start;
				for (int j = start; j < map[x][y].size(); j++) {
					int idx = map[x][y][j];
					horse[idx].x = nx;
					horse[idx].y = ny;
					map[nx][ny].push_back(idx);
				}
				while (num--) map[x][y].pop_back();
				if (map[nx][ny].size() >= 4) {
					cout << ans << "\n";
					return 0;
				}
				
			}
			// 이동할 칸이 빨간색인 경우
			else if (arr[nx][ny] == 1) {
				int num = map[x][y].size() - start;
				
				while (num!=0) {
					int idx = map[x][y].back();
					horse[idx].x = nx;
					horse[idx].y = ny;
					map[nx][ny].push_back(idx);
					map[x][y].pop_back();
					num--;
				}
				if (map[nx][ny].size() >= 4) {
					cout << ans << "\n";
					return 0;
				}
			}
		}
	
	}
	cout << -1 << "\n";
	return 0;
}
디버깅
  • 지문을 읽을 때, 말이 맨 아래에 있는 경우에만 이동이 가능한 것으로 착각을 하여 디버깅을 하는데 시간이 오래 걸렸습니다.
제출결과

0ms

마무리

지문을 꼼꼼하게 읽지 않으면 함정에 빠지기 쉬운문제이기 때문에 구현력을 키우는데 아주 좋은 문제인 것 같습니다.

 BOJ

Related Posts