[Algorithm][C++] SWEA 5650. [모의 SW 역량테스트] 핀볼 게임

url: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRF8s6ezEDFAUo 

SW Expert Academy

 

풀이 핵심

1. Back Tracking / Bruth Force 문제 (완전 탐색)

 

2. 벽을 만날 때 방향 전환을 어떻게 해주느냐가 핵심이다.

방향 배열을 다음과 같이 구성하면 그림에 표시된 주황색 방향과 같다.

...
const int dy[] = { 1,0,-1,0 };
const int dx[] = { 0,-1,0,1 };
...

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#define MAXN	100

int T, N, ans;
int map[MAXN][MAXN];

struct Info {
	int y, x, d;
};

struct _WormHole {
	int y, x, yy, xx;
};

_WormHole wormhole[10 + 1]; // Look Up Table
const int dy[] = { 1,0,-1,0 }; // 하, 좌, 상, 우
const int dx[] = { 0,-1,0,1 };

void init() { // 여러 개의 test case 대비 초기화
	ans = 0;
	for (int i = 6; i <= 10; i++) {
		wormhole[i].y = wormhole[i].x = \
			wormhole[i].yy = wormhole[i].xx = -1;
	}
}

int get_score(int sy, int sx, int sd) {
	int ret = 0;
	Info cur = { sy, sx, sd };
	while (1) {
		cur.y += dy[cur.d], cur.x += dx[cur.d];
		if ((cur.y == sy && cur.x == sx) || map[cur.y][cur.x] == -1) {
			break;
		}
		if (cur.y < 0 || cur.y >= N || cur.x < 0 || cur.x >= N || \
			map[cur.y][cur.x] == 5) {
			ret++;
			cur.d = (cur.d + 2) % 4;
			continue;
		}
		if (map[cur.y][cur.x] >= 1 && map[cur.y][cur.x] <= 4) {
			ret++;
			int block = map[cur.y][cur.x];
			if (cur.d == (block - 1)) {
				cur.d = ((block % 4) + 2) % 4;
			}
			else if (cur.d == (block % 4)) {
				cur.d = ((block - 1) + 2) % 4;
			}
			else {
				cur.d = (cur.d + 2) % 4;
			}
			continue;
		}
		if (map[cur.y][cur.x] >= 6 && map[cur.y][cur.x] <= 10) {
			int tag = map[cur.y][cur.x];
			if (cur.y == wormhole[tag].y && cur.x == wormhole[tag].x) {
				cur.y = wormhole[tag].yy;
				cur.x = wormhole[tag].xx;
			}
			else {
				cur.y = wormhole[tag].y;
				cur.x = wormhole[tag].x;
			}
		}
	}
	return ret;
}

void solve() {
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 0) {
				for (int dir = 0; dir < 4; dir++) {
					int candi = get_score(y, x, dir);
					if (candi > ans) ans = candi;
				}
			}
		}
	}
}

int main() {
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		init();
		scanf("%d", &N);
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				scanf("%d", &map[y][x]);
				if (map[y][x] >= 6 && map[y][x] <= 10) {
					int tag = map[y][x];
					if (wormhole[tag].y == -1) {
						wormhole[tag].y = y;
						wormhole[tag].x = x;
					}
					else {
						wormhole[tag].yy = y;
						wormhole[tag].xx = x;
					}
				}
			}
		}
		solve();
		printf("#%d %d\n", tc, ans);
	}
	return 0;
}

 

다른 종류의 벽들이 있기 때문에 조건에 따른 방향 전환만 잘 구현해주면 쉽게 풀 수 있다.