[백준] 17837번: 새로운 게임 2

https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

문제 이해

디버깅하는데 한참 걸린 문제였다. 근데 오래 걸린 이유가 애초에 처음 주어진 예제를 제대로 안살폈기 때문이다.

적어도 저렇게 문제에 친절하게 그림을 그려줬으면, 거기까지는 내 맵이 잘 맞아 떨어지는 지를 먼저 좀 보자!!!

 

말을 움직이는 게 힘든 문제이다.

말 구조체를

struct {
	int y, x, d;
	int idx; // 현재 위치의 밑으로부터 몇 번째인지
}

이렇게 정의했다. (y, x)는 좌표이고, d는 방향, idx는 현재 칸에 쌓인 말들 중 아래서부터 몇 번째 말인지를 저장한다. 이를 저장하는 이유는 옮길 때 내 위에 있는 말들을 같이 옮겨줘야 하기 때문이다.

말 구조체를 저장하는 mal 배열을 만들어줬다.

 

그리고 말이 어떻게 쌓여있는 지를 저장할 배열 map을 3차원으로 만들어줬다. map[r][c]는 (r,c)위치에 있는 말 리스트인데, 맨 밑부터 맨 위까지 차례대로 저장한다.

 

그리고 각 좌표 별 말의 개수를 저장할 cnt 배열을 만들어줬다. cnt[r][c]는 (r, c)에 쌓인 말의 개수이다. 

 

Move_Mals()

말의 방향에 따라서 다음 위치를 결정한다.

• 만약 a) 범위 외 b) 파란 칸 이면 방향을 바꿔서 현재 위치에서 다음 위치를 결정한다. 
  • 만약 방향을 바꿔서 가는 칸도 a) 범위 외 b) 파란 칸이면 움직이지 않는다. 
  • 새로운 위치로 움직이는 양상은 다음 칸이 하얀 칸인 경우와 같으니까 그 루트를 따르면 된다.

 

• 만약 빨간 칸이면 현재 위치에 나부터 내 위에 쌓은 말들을 역순으로 새로운 칸에 옮겨준다. 
  • 이를 위해 end와 start라는 map[cury][curx]에 있는 말 배열 범위를 지정해준다. (고정을 안시키면 말들을 옮기는 도중에 값이 변경되어서 제대로 옮길 수가 없다 ---> 이게 헤맨 원인이었다)
  • start는 현재 나의 인덱스 (mal[i].idx]이고 end는 (cury, curx)에 있는 말의 개수이다. 
  • end-1부터 start 까지 역순으로 map[ny][nx] 로 옮겨준다.

 

• 만약 하얀 칸이면 현재 위치에 나부터 내 위에 쌓은 말들을 순서대로 새로운 칸에 옮겨준다. 
  • 역시 end와 start를 고정해준다. 
  • start부터 end-1까지 map[ny][nx]로 옮겨준다. 
  • 이 움직임은 if(color[ny][nx] == WHITE)로 블럭화 하지 않는다. 왜냐하면 a) 범위 외 b) 파란 칸 인 경우에도 이 동작을 수행하기 때문이다. 대신 빨간 칸인 경우를 블럭화하고, 그 처리 후에 continue하도록 했다. 

 

int Move_Mals(void) {
	int result = 0;
	for (int i = 1; i <= K; i++) {
		int ny = mal[i].y + dy[mal[i].d];
		int nx = mal[i].x + dx[mal[i].d];
		if ((ny < 1 || ny > N || nx < 1 || nx > N) || color[ny][nx] == BLUE) {
			mal[i].d = rev[mal[i].d];
			ny = mal[i].y + dy[mal[i].d];
			nx = mal[i].x + dx[mal[i].d];
			if ((ny < 1 || ny > N || nx < 1 || nx > N) || (color[ny][nx] == BLUE)) {
				if (cnt[ny][nx] >= 4) {
					//Print_Map();
					return 1;
				}
				continue; // 움직이지 않음
			}
		}
		if (color[ny][nx] == RED) {
			// (ny, nx)로 이동한다, 단, 반대방향으로 쌓임
			int end = cnt[mal[i].y][mal[i].x];
			int start = mal[i].idx;
			int cury = mal[i].y, curx = mal[i].x;
			for (int j = end-1; j >= start; j--) {
				// 말 번호는 map[mal[i].y][mal[i].x][j]
				int no = map[cury][curx][j];
				// 전에 거 지움
				map[cury][curx][j] = 0;
				cnt[cury][curx]--;
				// 새로운 곳에 갖다 넣음 
				map[ny][nx][cnt[ny][nx]] = no;
				mal[no].idx = cnt[ny][nx];
				mal[no].y = ny, mal[no].x = nx;
				cnt[ny][nx]++;
			}
			if (cnt[ny][nx] >= 4) {
				//Print_Map();
				return 1;
			}
			continue;
		}
		// else if (color[ny][nx] == WHITE)
		// (ny, nx)로 이동한다
		int end = cnt[mal[i].y][mal[i].x];
		int start = mal[i].idx;
		int cury = mal[i].y, curx = mal[i].x;
		for(int j = start; j<end; j++){
			// 말 번호는 map[mal[i].y][mal[i].x][j]
			int no = map[cury][curx][j];
			// 전에 거 지움
			map[cury][curx][j] = 0;
			cnt[cury][curx]--;
			// 새로운 곳에 갖다 넣음 
			map[ny][nx][cnt[ny][nx]] = no;
			mal[no].idx = cnt[ny][nx];
			mal[no].y = ny, mal[no].x = nx;
			cnt[ny][nx]++;
			if (cnt[ny][nx] >= 4) {
				//Print_Map();
				return 1;
			}
		}

	}
	return 0;
}

이 함수는 값을 리턴한다. 만약에 말을 하나하나 움직이던 도중에, 쌓인 말의 개수가 4개 이상이 되면 더 이상 진행하지 않고 1를 리턴하여 모든 과정을 종료하도록 한다. 

여기서 한 turn을 마친 후에 이걸 체크하는 것이 아니라 말을 하나씩 움직일 때마다 확인을 해줘야 한다!!!

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 12
#define MAXK 10
#define WHITE 0
#define RED 1
#define BLUE 2

int N, K; // 판 크기, 말의 개수
int color[MAXN + 5][MAXN + 5];
int map[MAXN + 5][MAXN + 5][MAXK+5];
int cnt[MAXN + 5][MAXN + 5];
struct {
	int y, x, d;
	int idx; // 현재 위치의 밑으로부터 몇 번째인지
}mal[MAXK+5];
//→, ←, ↑, ↓
int dy[] = { 0, 0, -1, 1 };
int dx[] = { 1, -1, 0, 0 };
int rev[] = { 1, 0, 3, 2 };

void Print_Map(void) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%d ", cnt[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}


void Get_Input(void) {
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &color[i][j]);
		}
	}
	for (int i = 1; i <= K; i++) {
		scanf("%d %d %d", &mal[i].y, &mal[i].x, &mal[i].d);
		mal[i].d--;
		int y = mal[i].y, x = mal[i].x;
		map[y][x][cnt[y][x]] = i;
		mal[i].idx = cnt[y][x];
		cnt[y][x]++;
	}
}

int Move_Mals(void) {
	int result = 0;
	for (int i = 1; i <= K; i++) {
		int ny = mal[i].y + dy[mal[i].d];
		int nx = mal[i].x + dx[mal[i].d];
		if ((ny < 1 || ny > N || nx < 1 || nx > N) || color[ny][nx] == BLUE) {
			mal[i].d = rev[mal[i].d];
			ny = mal[i].y + dy[mal[i].d];
			nx = mal[i].x + dx[mal[i].d];
			if ((ny < 1 || ny > N || nx < 1 || nx > N) || (color[ny][nx] == BLUE)) {
				if (cnt[ny][nx] >= 4) {
					//Print_Map();
					return 1;
				}
				continue; // 움직이지 않음
			}
		}
		if (color[ny][nx] == RED) {
			// (ny, nx)로 이동한다, 단, 반대방향으로 쌓임
			int end = cnt[mal[i].y][mal[i].x];
			int start = mal[i].idx;
			int cury = mal[i].y, curx = mal[i].x;
			for (int j = end-1; j >= start; j--) {
				// 말 번호는 map[mal[i].y][mal[i].x][j]
				int no = map[cury][curx][j];
				// 전에 거 지움
				map[cury][curx][j] = 0;
				cnt[cury][curx]--;
				// 새로운 곳에 갖다 넣음 
				map[ny][nx][cnt[ny][nx]] = no;
				mal[no].idx = cnt[ny][nx];
				mal[no].y = ny, mal[no].x = nx;
				cnt[ny][nx]++;
			}
			if (cnt[ny][nx] >= 4) {
				//Print_Map();
				return 1;
			}
			continue;
		}
		// else if (color[ny][nx] == WHITE)
		// (ny, nx)로 이동한다
		int end = cnt[mal[i].y][mal[i].x];
		int start = mal[i].idx;
		int cury = mal[i].y, curx = mal[i].x;
		for(int j = start; j<end; j++){
			// 말 번호는 map[mal[i].y][mal[i].x][j]
			int no = map[cury][curx][j];
			// 전에 거 지움
			map[cury][curx][j] = 0;
			cnt[cury][curx]--;
			// 새로운 곳에 갖다 넣음 
			map[ny][nx][cnt[ny][nx]] = no;
			mal[no].idx = cnt[ny][nx];
			mal[no].y = ny, mal[no].x = nx;
			cnt[ny][nx]++;
			if (cnt[ny][nx] >= 4) {
				//Print_Map();
				return 1;
			}
		}

	}
	return 0;
}

int main(void) {
	int t;
	freopen("in.txt", "r", stdin);
	Get_Input();
	//Print_Map();
	for (t = 1; t <= 1000; t++) {
		if(Move_Mals() == 1) break;
		//Print_Map();
	}
	if (t > 1000) printf("-1");
	else printf("%d", t);
	return 0;
}