[Algorithm][C++] BOJ 17837 새로운 게임 2

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

17837번: 새로운 게임 2

na982님 풀이 참고

https://na982.tistory.com/118

[삼성 SW 역량 테스트] 새로운 게임 2

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

struct POS { int r, c, d; };
const int dr[] = { 0,0,-1,1 };
const int dc[] = { 1,-1,0,0 };

int n, k;
int color[12][12];
int map[12][12][5];

int pos_size;
POS pos[10];

int turn(int index) {
	POS cur = pos[index];
	POS next;
	next.r = cur.r + dr[cur.d];
	next.c = cur.c + dc[cur.d];
	next.d = cur.d;
	if (next.r < 0 || next.r >= n || next.c < 0 || next.c >= n || color[next.r][next.c] == 2) {
		next.d = ((cur.d == 0 || cur.d == 2) ? (cur.d + 1) : (cur.d - 1));
		next.r = cur.r + dr[next.d];
		next.c = cur.c + dc[next.d];
		pos[index].d = next.d;
		if (next.r < 0 || next.r >= n || next.c < 0 || next.c >= n || color[next.r][next.c] == 2) {
			return map[cur.r][cur.d][0];
		}
	}

	int bottom = -1;
	int& cur_size = map[cur.r][cur.c][0];
	for (int i = 1; i <= cur_size; i++) {
		if (map[cur.r][cur.c][i] == index) {
			bottom = i;
			break;
		}
	}

	int move[5] = { 0, };
	int& move_size = move[0];
	for (int i = bottom; i <= cur_size; i++) {
		move[++move_size] = map[cur.r][cur.c][i];
	}
	cur_size = bottom - 1;

	if (color[next.r][next.c] == 1) {
		for (int i = 1; i <= move_size / 2; i++) {
			int temp = move[i];
			move[i] = move[move_size - i + 1];
			move[move_size - i + 1] = temp;
		}
	}

	int& next_size = map[next.r][next.c][0];
	for (int i = 1; i <= move_size; i++) {
		map[next.r][next.c][++next_size] = move[i];
		pos[move[i]].r = next.r;
		pos[move[i]].c = next.c;
		if (next_size >= 4) return next_size;
	}
	return next_size;
}

int main() {
	scanf("%d %d", &n, &k);
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			scanf("%d", &color[r][c]);
		}
	}
	for (int i = 0; i < k; i++) {
		int r, c, d;
		scanf("%d %d %d", &r, &c, &d);
		--r, --c, --d;
		pos[pos_size].r = r;
		pos[pos_size].c = c;
		pos[pos_size].d = d;
		int& size = map[r][c][0];
		map[r][c][++size] = pos_size;
		++pos_size;
	}

	int loop = 0, ret = -1;
	while (loop <= 1000 && ret == -1) {
		++loop;
		for (int i = 0; i < k; i++) {
			int h = turn(i);
			if (h >= 4) {
				ret = loop;
				break;
			}
		}
	}
	printf("%d", ret);
	return 0;
}

 

아쉬운 점

1. 더블링크드리스트로 풀려고 열심히 코드를 짰는데 틀려서 풀 마음이 팍 식어버렸다..

2. 그냥 링크드리스트 오랜만에 다시 공부했다고 생각해야겠다.

3. na982님 풀이중 & 연산자 활용이 가장 마음에 들었다.