리팩토링 이전
Connect four 게임에서 마커가 4개 이상 연결되었는지를 체크하는 로직을 작성하기 위하여, 1차적으로 코드를 작성해 보았다.
- 열과 행의 숫자를 가져와서 해당 숫자를 기준으로 반복문을 돌면서 연속된 마커 개수를 체크한다.
- 만약 마커 옆에 다른 마커가 있다면,
break로 중지한다. - 카운트가 4개 되면 해당 유저가 승리한다.
// src/slices/gameSlice.ts
drop: (state, actions) => {
if (state.winner !== null) {
console.warn(`이미 종료된 게임입니다. 승자는 ${state.winner}입니다.`);
return;
}
if (state.board[actions.payload.lineNumber][0] !== null) {
console.warn(
`${actions.payload.lineNumber + 1} 열은 이미 전부 채워진 열입니다.`
);
return;
}
let location = null;
/**
* 만약 선택한 행의 첫 번째 셀이 null이 아니면 리턴.
* TODO: 위 경우 다시 마커를 둘 수 있도록 처리해야 한다.
*/
for (let i = 6; i >= 0; i--) {
if (state.board[actions.payload.lineNumber][i] === null) {
state.board[actions.payload.lineNumber][i] =
state.currentPlayer === "RED" ? "RED" : "YELLOW";
location = i;
break;
}
}
state.markerCount += 1;
let rowCount = 1;
let colCount = 1;
if (state.markerCount >= 7) {
for (let i = 1; i <= 3; i++) {
if ((rowCount || colCount) >= 4) {
break;
}
// 가로 테스트
if (
actions.payload.lineNumber + i <= 6 &&
state.board[actions.payload.lineNumber + i][location!] ===
actions.payload.player
) {
rowCount += 1;
} else {
break;
}
}
for (let i = 1; i <= 3; i++) {
if ((rowCount || colCount) >= 4) {
break;
}
if (
actions.payload.lineNumber - i >= 0 &&
state.board[actions.payload.lineNumber - i][location!] ===
actions.payload.player
) {
rowCount += 1;
} else {
break;
}
}
// 세로 테스트
for (let i = 1; i <= 3; i++) {
if ((rowCount || colCount) >= 4) {
break;
}
if (
location! + i <= 5 &&
state.board[actions.payload.lineNumber][location! + i] ===
actions.payload.player
) {
colCount += 1;
} else {
break;
}
}
for (let i = 1; i <= 3; i++) {
if ((rowCount || colCount) >= 4) {
break;
}
if (
location! - i >= 5 &&
state.board[actions.payload.lineNumber][location! - i] ===
actions.payload.player
) {
colCount += 1;
} else {
break;
}
}
// TODO: 대각선 테스트
if (colCount >= 4 || rowCount >= 4) {
state.winner = actions.payload.player;
}
}
state.currentPlayer = actions.payload.player === "RED" ? "YELLOW" : "RED";
},
문제점
위 코드의 문제점은 반복된 코드가 많고, 대각선은 한 번에 4번을 테스트해야 한다는 것에 있다.
다행히, 중첩 반복문은 존재하지 않지만 가로/세로 체크에 각각 2번, 거기에 대각선까지 4번의 반복문을 작성해야 한다는 점에서 비슷한 코드가 반복된다는 점에서 가독성도 낮고 좋지 않은 코드라고 볼 수 있다.
이러한 문제점을 해결하기 위해 고민하던 중, 코딩 테스트에 자주 등장하는 섬의 개수와 비슷한 방법으로 해결하면 좋지 않을까, 하는 생각이 들어 direction vector을 적용해 보기로 했다.
섬의 개수는 이중 배열 내에 있는 모든 값을 탐색하고, 섬일 경우를 체크하는 로직을 사용한다. 섬은 상하좌우/대각선으로 이루어져 있다.
내 경우는 최근에 둔 마커를 기준으로 마찬가지로 상하좌우 대각선 모든 방향을 탐색할 수 있도록 처리하고, 다른 사람이 둔 마커와 빈 공간을 바다라고 생각하고 처리하면 될 것 같다는 생각이 들어 이 방식을 선택했다.
direction vector
여기에 추가로 연결되어 있는 것만 체크해 준다.
승리 조건 테스트를 위해 모든 방향을 체크해 주어야 한다.
// brute.ts
const board = [
[null, null, null, null, null, null],
[null, null, null, null, null, null],
[null, null, null, null, null, null],
[null, null, null, null, null, null],
[null, null, null, null, null, null],
[null, null, null, null, null, null],
["RED", null, "RED", "RED", null, null],
] as (null | "RED" | "YELLOW")[][];
// 모든 방향을 체크하기 위해 방향 벡터를 사용한다.
const movement = [
{ dx: 1, dy: 0 }, // 오른쪽
{ dx: -1, dy: 0 }, // 왼쪽
{ dx: 0, dy: 1 }, // 위
{ dx: 0, dy: -1 }, // 아래
{ dx: 1, dy: 1 }, // 오른쪽 아래 대각선
{ dx: -1, dy: 1 }, // 왼쪽 아래 대각선
{ dx: 1, dy: -1 }, // 오른쪽 위 대각선
{ dx: -1, dy: -1 }, // 왼쪽 위 대각선
];
let x = 6;
let y = 1;
let currentPlayer = "RED";
const checkDirection = (x: number, y: number, dx: number, dy: number) => {
let count = 1; // 기존 마커도 추가.
let nx = x + dx; // X축 각 방향별로 1칸씩 이동
let ny = y + dy; // Y축 각 방향별로 1칸씩 이동
while (
// 각 좌표가 보드 내에 있고, 해당 위치에 있는 마커가 현재 유저의 마커와 같은 색상의 마커인지 확인한다.
// 만약 마커가 보드를 넘어갈 경우, 종료.
nx >= 0 &&
ny >= 0 &&
nx <= 6 &&
ny <= 5 &&
board[nx][ny] === currentPlayer
) {
count++;
nx += dx;
ny += dy;
}
return count;
};
for (const { dx, dy } of movement) {
const count = checkDirection(x, y, dx, dy);
if (count >= 4) {
console.log(`${currentPlayer}가 승리했습니다.`);
break;
}
}
위 코드에서는 위, 아래, 오른쪽, 왼쪽, 오른쪽 아래, 오른쪽 위, 왼쪽 위, 왼쪽 아래 대각선을 모두 체크해 준다.
로직은 다음과 같다.
- 이동해야 하는 방향 벡터를 담은 배열을 만들어 준다.
- 배열에 반복문으로 각 방향 벡터를 하나씩 전달해 준다. 이 방향 값을 가지고, 한 칸씩 이동하면서 연결되어 있는 마커를 체크한다.
- 이 때 체크하는 칸에 다른 색상의 마커가 있거나, 보드의 너비를 넘었을 경우, 종료한다.
- 어느 한 방향이라도
count가 4 이상일 경우, 조건을 충족하므로 종료시킨다.
문제점
이 방식의 문제점은, 연결을 테스트하는 로직을 한 방향으로만 테스트한다는 것이다. 위에 있는 board에서처럼 ["RED", null, "RED", "RED", null, null]로 이루어져 있고, board[6][1]의 칸에 두면 분명 4개의 마커가 이어져 있는데도, 카운트를 한 방향으로만 하기 때문에 승자로 처리하지 않는다.
해결
방향 탐색을 가로, 세로, 양수 대각선, 음수 대각선으로 지정하고 두 번 계산한다.
// brute.ts
drop: (state, actions) => {
if (state.winner !== null) {
console.warn(`이미 종료된 게임입니다. 승자는 ${state.winner}입니다.`);
return;
}
if (state.board[actions.payload.lineNumber][0] !== null) {
console.warn(
`${actions.payload.lineNumber + 1} 열은 이미 전부 채워진 열입니다.`
);
return;
}
let location: null | number = null;
/**
* 만약 선택한 행의 첫 번째 셀이 null이 아니면 리턴.
*/
for (let i = 6; i >= 0; i--) {
if (state.board[actions.payload.lineNumber][i] === null) {
state.board[actions.payload.lineNumber][i] =
state.currentPlayer === "RED" ? "RED" : "YELLOW";
location = i;
break;
}
}
state.markerCount += 1;
// 모든 방향을 체크하기 위해 방향 벡터를 사용한다.
const movement = [
{ dx: 1, dy: 0 }, // 가로
{ dx: 0, dy: 1 }, // 세로
{ dx: -1, dy: 1 }, // 양수 대각선
{ dx: -1, dy: -1 }, // 음수 대각선
];
// 연결 테스트
const checkDirection = (dx: number, dy: number) => {
let count = 1; // 기존 마커도 추가.
let pnx = actions.payload.lineNumber + dx; // X축 각 방향별로 1칸씩 이동
let pny = location! + dy; // Y축 각 방향별로 1칸씩 이동
while (
// 각 좌표가 보드 내에 있고, 해당 위치에 있는 마커가 현재 유저의 마커와 같은 색상의 마커인지 확인한다.
// 만약 마커가 보드를 넘어갈 경우, 종료.
pnx >= 0 &&
pny >= 0 &&
pnx <= 6 &&
pny <= 5 &&
state.board[pnx][pny] === actions.payload.player
) {
count++;
pnx += dx;
pny += dy;
}
let mnx = actions.payload.lineNumber - dx; // X축 각 방향별로 1칸씩 이동
let mny = location! - dy; // Y축 각 방향별로 1칸씩 이동
while (
// 각 좌표가 보드 내에 있고, 해당 위치에 있는 마커가 현재 유저의 마커와 같은 색상의 마커인지 확인한다.
// 만약 마커가 보드를 넘어갈 경우, 종료.
mnx >= 0 &&
mny >= 0 &&
mnx <= 6 &&
mny <= 5 &&
state.board[mnx][mny] === actions.payload.player
) {
count++;
mnx -= dx;
mny -= dy;
}
return count;
};
for (const { dx, dy } of movement) {
const count = checkDirection(dx, dy);
if (count >= 4) {
state.winner = actions.payload.player;
console.log(`${state.winner}가 승리했습니다.`);
return;
}
}
state.currentPlayer = actions.payload.player === "RED" ? "YELLOW" : "RED";
},