static int N;
static int board[100][100];
static int map_y[11][100];
static int map_x[11][100];
static int d[4][2] = {
-1, 0, //up, 0
1, 0, //down, 1
0, -1, //left, 2
0, 1 //right, 3
};
static int changed[4][6] = {
1, 1, 3, 2, 1, 1,
0, 3, 0, 0, 2, 0,
3, 0, 1, 3, 3, 3,
2, 2, 2, 1, 0, 2
};
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 get_result(int y, int x, int dir)
{
int ret = 0;
int cy = y, cx = x;
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 && board[cy][cx] <= 10) //웜홀
{
int ccy = cy, ccx = cx; //현재 위치 저장
cy = map_y[board[ccy][ccx]][ccy];
cx = map_x[board[ccy][ccx]][ccx];
}
else if (board[cy][cx] == -1) //블랙홀
break;
} while (!(cy == y && cx == x)); //출발 위치가 아니면 반복
return ret;
}
static int solution(void)
{
int max = 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 && board[y][x] <= 10) //웜홀
q[board[y][x]].push({ y, x });
}
}
for (int i = 6; i <= 10; i++)
{
if (q[i].size())
{
pair<int, int> p1 = q[i].front();
q[i].pop();
pair<int, int> p2 = q[i].front();
q[i].pop();
map_y[i][p1.first] = p2.first;
map_y[i][p2.first] = p1.first;
map_x[i][p1.second] = p2.second;
map_x[i][p2.second] = p1.second;
}
}
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 = get_result(y, x, dir);
if (ret > max)
max = ret;
}
}
}
return max;
}최대, 최소 구하는 문제는 가급적 모든 경우를 다 확인 해보는 것이 구현하기에 제일 빠르고 안전하다 볼 수 있다.
그래서 출발할 수 있는 모든 위치에서 모든 방향으로 다 가보고 그 때의 결과 중 최대 값만 선별하여 해당 값을 반환 한다.
먼저 changed에 대해서는 움직이는 방향이 특정 벽을 만나면 특정 방향으로 바뀐다.
row 인덱스는 현재 방향을 의미하고, column 인덱스는 어떤 벽을 만났는지를 의미한다.
그래서 0(up) 이 일반블록이 아닌 벽을 만나면 (0) changed[0][0]으로 접근해서 1(down)으로 그 방향이 바뀌게 된다.
웜홀은 항상 쌍으로 주어지며, 그 때의 값은 서로 같다. 그래서 q배열은 해당 값을 인덱스로 하여 그 때의 좌표 값을 저장한다. 그래서 q[i]의 element가 있다는 것은 항상 2개의 좌표 정보가 있음을 의미한다.
여기서 map_y는 현재 웜홀의 y좌표를 다른 웜홀의 y좌표로 변환 시켜주며, map_x는 x좌표에 대해서 변환 시켜준다.
코드를 정리하다 보니 해당 웜홀이 어떤 값을 갖는지를 의미하는 row인덱스는 필요 없는 듯 하다.
특정 웜홀의 y, x 좌표는 유일하기 때문이다.
이어서 핵심이라 할 수 있는 get_result()에 대해서 이다.
먼저 좌표는 항상 변해야 한다. 심지어 해당 좌표가 게임을 진행하는 board의 외부에 있어도 말이다.
아래의 경우에 대해서 생각해보면,
정확한 순서는 위와 같다. 그러나 좌표위치를 매번 갱신하지 않으면,
이렇게 되어 벽에 부딪혀 방향이 바뀌기는 하지만 블록에 부딪혀 방향이 바뀌지는 않게 된다.
마지막은 반복의 조건이다.
반복의 조건을 좀 대강 생각해서 문제가 되기도 했다.
처음에는 (y != cy && x != cx) 일 때 반복하도록 하였다. 괜히 괄호치고 ! 쓰기가 귀찮아서 착각하고 실수한 부분이었다.
항상 실수하지 않기 위해서는 되도록 조건을 되도록 생각한 바 대로 구현해야 겠다.
(cy, cx가 y, x와 같지 않다면 반복) -> !(cy == y && cx == x)