SW Expert Academy - 5650. 핀볼 게임

문제링크

• 핀볼 게임

문제접근

• 재귀호출 을 하게 되면 런타임 에러가 발생한다. 반복문 으로 풀도록 하자.
• 웜홀의 위치 정보는 미리 배열에 담아두고, 웜홀 번호에 맞는 좌표 정보를 빠르게 찾아올 수 있도록 한다.
• 블록의 모양에 따라 방향이 바뀌는데, 어떤 방향에서 부딪혔는지에 따라서도 변화하는 방향이 다르기 때문에 유의해야 한다.

구현

#include <iostream>
#include <memory.h>
#include <vector>
#include <queue>
#include <algorithm>

#define MAX_N 100
#define MAX_WORM 11
#define BLACK_HOLE -1
#define EMPTY 0

#define BLOCK_ONE 1
#define BLOCK_TWO 2
#define BLOCK_THREE 3
#define BLOCK_FOUR 4
#define BLOCK_FIVE 5

#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3

using namespace std;

int N;
int board[MAX_N][MAX_N];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<pair<int, int>> startPoints;
vector<pair<int, int>> wormTable[MAX_WORM];
int startX, startY;
int ans = 0;

void init()
{
	memset(board, 0, sizeof(board));
	startPoints.clear();
	ans = 0;
	for (int i = 0; i < MAX_WORM; i++) {
		wormTable[i].clear();
	}
}

void input()
{
	init();
	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> board[r][c];
			if (board[r][c] == EMPTY) startPoints.push_back(make_pair(r, c));
			else if (board[r][c] > BLOCK_FIVE) wormTable[board[r][c]].push_back(make_pair(r, c));
		}
	}
}

int getReverseDir(int dir)
{
	if (dir == UP) return DOWN;
	if (dir == DOWN) return UP;
	if (dir == LEFT) return RIGHT;
	if (dir == RIGHT) return LEFT;
}

int getDirBlockOne(int dir)
{
	if (dir == DOWN) return RIGHT;
	if (dir == LEFT) return UP;
	return getReverseDir(dir);
}

int getDirBlockTwo(int dir)
{
	if (dir == UP) return RIGHT;
	if (dir == LEFT) return DOWN;
	return getReverseDir(dir);
}

int getDirBlockThree(int dir)
{
	if (dir == UP) return LEFT;
	if (dir == RIGHT) return DOWN;
	return getReverseDir(dir);
}

int getDirBlockFour(int dir)
{
	if (dir == RIGHT) return UP;
	if (dir == DOWN) return LEFT;
	return getReverseDir(dir);
}

int getDirBlockFive(int dir)
{
	return getReverseDir(dir);
}

void passWormHole(int wormNum, int cx, int cy, int& nx, int& ny)
{
	for (int i = 0; i < wormTable[wormNum].size(); i++) {
		pair<int, int> wormPos = wormTable[wormNum][i];
		if (cx == wormPos.first && cy == wormPos.second) continue;
		nx = wormPos.first;
		ny = wormPos.second;
	}
}

void playGame(int xpos, int ypos, int dir)
{
	int score = 0;
	int cx = xpos;
	int cy = ypos;
	int cdir = dir;
	int nx, ny;
	int cnt = 0;
	while (true) {
		ans = max(ans, score);
		nx = cx + dx[cdir];
		ny = cy + dy[cdir];

		if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
			cdir = getReverseDir(cdir);
			cx = nx; 
			cy = ny;
			score++;
			continue;
		}

		if (nx == startX && ny == startY) break;
		if (board[nx][ny] == BLACK_HOLE) break;

		if (board[nx][ny] <= BLOCK_FIVE && board[nx][ny] >= BLOCK_ONE) {
			score++;
			if (board[nx][ny] == BLOCK_ONE) cdir = getDirBlockOne(cdir);
			else if (board[nx][ny] == BLOCK_TWO) cdir = getDirBlockTwo(cdir);
			else if (board[nx][ny] == BLOCK_THREE) cdir = getDirBlockThree(cdir);
			else if (board[nx][ny] == BLOCK_FOUR) cdir = getDirBlockFour(cdir);
			else if (board[nx][ny] == BLOCK_FIVE) cdir = getDirBlockFive(cdir);
		}
		else if (board[nx][ny] > BLOCK_FIVE) { // 웜홀
			int wormNum = board[nx][ny];
			int wormX = nx;
			int wormY = ny;
			passWormHole(wormNum, wormX, wormY, nx, ny);
		}
		cx = nx;
		cy = ny;
	}
}

void solution()
{
	for (auto ele : startPoints) {
		startX = ele.first;
		startY = ele.second;
		for (int dir = 0; dir < 4; dir++) {
			playGame(ele.first, ele.second, dir);
		}
	}
}

void test()
{
	input();
	for (auto ele : startPoints) {
		startX = ele.first;
		startY = ele.second;
		for (int dir = 0; dir < 4; dir++) {
			playGame(ele.first, ele.second, dir);
			cout << ans << endl;
		}
		break;
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	// test();
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		solution();
		cout << "#" << test_case << " " << ans << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}