5650. 핀볼게임

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

using namespace std;

static int N;
static int board[100][100];
static int d[4][2] = {
	-1, 0,
	1, 0,
	0, -1,
	0, 1
}; //row: y, column: x
static int changed[4][6] = {
	DOWN, DOWN, RIGHT, LEFT, DOWN, DOWN,
	UP, RIGHT, UP, UP, LEFT, UP,
	RIGHT, UP, DOWN, RIGHT, RIGHT, RIGHT,
	LEFT, LEFT, LEFT, DOWN, UP, LEFT
}; //row: current direction, column: object -> changed direction
static int map_y[11][100]; //row: worm hole number, column: current y -> mapped y
static int map_x[11][100]; //row: worm hole number, column: current x -> mapped x

static bool out_of_bound(int y, int x)
{
	if (y < 0 || y >= N)
		return true;
	if (x < 0 || x >= N)
		return true;
	return false;
}

static int __solution(int y, int x, int dir)
{
	int cy = y, cx = x;
	int ret = 0;

	do
	{
		cy += d[dir][0];
		cx += d[dir][1];

		if (out_of_bound(cy, cx)) //범위 체크는 제일 먼저
		{
			ret += 1; //점수 상승
			dir = changed[dir][0]; //방향 변경
		}
		else if (board[cy][cx] >= 1 && board[cy][cx] <= 5) //블록을 만났다면
		{
			ret += 1; //점수 상승
			dir = changed[dir][board[cy][cx]]; //방향 변경
		}
		else if (board[cy][cx] >= 6) //웜홀이라면
		{
			int worm = board[cy][cx];
			cy = map_y[worm][cy]; //점프
			cx = map_x[worm][cx]; //점프
		}
		else if (board[cy][cx] == -1) //블랙홀이라면
			break;

	} while (!(cy == y && cx == x)); //시작위치로 돌아오지 않았다면 반복,

	return ret;
}

static int solution()
{
	int ans = 0;
	queue<pair<int, int>> q[11];

	scanf("%d", &N);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			scanf("%d", &board[y][x]);
			if (board[y][x] >= 6) //worm hole
				q[board[y][x]].push({ y, x });
		}
	}

	for (int n = 6; n <= 10; n++)
	{
		if (q[n].empty())
			continue;

		pair<int, int> w1 = q[n].front();
		q[n].pop();
		pair<int, int> w2 = q[n].front();
		q[n].pop();

		map_y[n][w1.first] = w2.first;
		map_y[n][w2.first] = w1.first;
		map_x[n][w1.second] = w2.second;
		map_x[n][w2.second] = w1.second;
	}

	//모든 y, x와 방향에 대해서 체크해야함
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			//블록, 웜홀, 블랙홀이 있는 위치에서는 출발 할 수 없음,
			if (board[y][x] != 0)
				continue; 

			for (int dir = 0; dir < 4 ; dir++)
			{
				int ret = __solution(y, x, dir);
				if (ret > ans)
					ans = ret;
			}
		}
	}

	return ans;
}

비교적 최근에 풀었던 문제여서 다시 코드를 작성하는데 큰 어려움은 없었다.

다만, 예전에 작성했던 글에서는 map_y, map_x 이차원 배열이 아닌 일차원 배열로 해도 무방할 것 같다고 작성을 하였는데, 이는 틀린 말이었다.

 

(y, x)로 좌표를 표현 할 때,

(5, 10) <-> (7, 8)

(9, 3) <-> (5, 8) 

이렇게 웜홀을 통과 한다고 하면,

첫번째 웜홀 처리를 위해 저장된 값이 뒤이어 오는 웜홀 처리를 위한 값으로 덮어씌워지게 된다.

 

그래서 웜홀 번호를 같이 이용하여 map_y, map_x를 이차원 배열로 하는게 맞다.

 

//주의사항 및 정리

1. 이차원 배열에서 어떠한 방향으로든지 순회 시에는 배열 범위를 체크하는 것이 항상 먼저 와야 한다.

2. 반복의 조건은 항상 신중하게 작성해야 한다. 최대한 이해하기 쉽게 작성할것.

3. 최대, 최소 구하는 문제는 가급적 모든 경우를 다 따져보는 것이 좋으며, 그러기 위해서는 입력의 조건도 같이 따져봐야 한다.

4. 문제 제대로 읽기.