SWEA5650

23 Jan 2020 • ProblemSolving

핀볼게임

문제출처

1.설계(15분)

  • 문제 해석

    • 핀볼은 임의의 좌표에서 상하좌우 중 한방향으로 움직일 수 있습니다.
    • 벽이나 블록(1~5)에 부딪히면 각 모양에 맞게 반사되어 움직입니다.
    • 웜홀(6~10)에 빠지면 동일한 숫자를 가진 다른 웜홀로 빠져나옵니다.
    • 출발 위치로 돌아오거나 블랙홀(-1)을 만나면 게임이 종료됩니다.
    • 핀볼을 움직여서 최대 점수(벽or 블록에 부딪힌 횟수)를 구하는 문제입니다.
    • 1 <= N <= 100

  • 설계

    • 전체 범위의 빈공간에서 4 방향으로 핀볼게임을 진행해주면 됩니다.
    • 각 블록의 모양에 맞게 방향전환만 해주면 됩니다.

2.구현(35분)

  • 코드
#include <iostream>
#include <algorithm>
#define MAXN 100
using namespace std;

struct node {
	int x1;
	int y1;
	int x2;
	int y2;
	
};
node hole[5];

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

int N;
int map[MAXN][MAXN];

int block(int idx, int dir) {
	if (idx == 1) {
		if (dir == 0) return 2;
		else if (dir == 1) return 0;
		else if (dir == 2) return 3;
		return 1;
	}
	else if (idx == 2){
		if (dir == 0) return 2;
		else if (dir == 1) return 3;
		else if (dir == 2) return 1;
		return 0;
	}
	else if (idx == 3) {
		if (dir == 0) return 1;
		else if (dir == 1) return 3;
		else if (dir == 2) return 0;
		return 2;
	}
	else if (idx == 4) {
		if (dir == 0) return 3;
		else if (dir == 1) return 2;
		else if (dir == 2) return 0;
		return 1;
	}
	
	return (dir + 2) % 4;

}

int simulate(int x, int y, int dir) {
	int sum = 0;
	int nx = x;
	int ny = y;
	while (1) {
		nx += dx[dir];
		ny += dy[dir];
		if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
			dir = (dir + 2) % 4;
			sum++;
			continue;
		}
		if ((nx == x && ny == y) || map[nx][ny] == -1) return sum;
		if (1 <= map[nx][ny] && map[nx][ny] <= 5) {
			dir = block(map[nx][ny], dir);
			sum++;
		}
		else if (map[nx][ny]>=6){
			
			if (hole[map[nx][ny] - 6].x1 == nx && hole[map[nx][ny] - 6].y1 == ny) {
				int tmp_nx = hole[map[nx][ny] - 6].x2;
				int tmp_ny = hole[map[nx][ny] - 6].y2;
				nx = tmp_nx;
				ny = tmp_ny;
			}
			else {
				int tmp_nx = hole[map[nx][ny] - 6].x1;
				int tmp_ny = hole[map[nx][ny] - 6].y1;
				nx = tmp_nx;
				ny = tmp_ny;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	for (int test_case = 1; test_case <= t; test_case++) {
		for (int i = 0; i < 5; i++) {
			hole[i] = { -1,-1,-1,-1 };
		}
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> map[i][j];
				if (map[i][j] >= 6) {
					if (hole[map[i][j] - 6].x1 == -1) {
						hole[map[i][j] - 6].x1 = i;
						hole[map[i][j] - 6].y1 = j;
					}
					else {
						hole[map[i][j] - 6].x2 = i;
						hole[map[i][j] - 6].y2 = j;
					}
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0) continue;
				for (int k = 0; k < 4; k++) {
					ans = max(ans, simulate(i, j, k));
				}
			}
		}
		cout << "#"<< test_case<<" "<< ans << "\n";
	}
	
	return 0;
}

  • 디버깅

    • 벽에 부딪혔을 경우에 바로 반대방향으로 움직이게 구현을 해서 에러가 났습니다. 부딪히면 방향만 바꾸고 바로 continue로 진행하도록 수정 하였습니다.

  • 제출결과

    164ms

3.마무리

  • 별다른 어려움이 없었던 시뮬레이션 문제였습니다. 하지만 구현을 빠르게 하지 못해서 30분안에 풀지 못하였습니다.
 SWEA

Related Posts