[백준] 2615 오목 - javascript

📌 문제

https://www.acmicpc.net/problem/2615

📌 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

const board = input.map((i) => i.split(' ').map(Number));
const dx = [1, 1, 0, -1];
const dy = [0, 1, 1, 1];
let ans = 0;
let ansX, ansY;

function check(x, y, color) {
  for (let i = 0; i < 4; i++) {
    let [nx, ny] = [x + dx[i], y + dy[i]];
    let cnt = 1;

    while (1) {
      if (ny < 0 || ny >= 19 || nx < 0 || nx >= 19) break;

      if (board[nx][ny] !== color) {
        break;
      }
      cnt++;
      nx = nx + dx[i];
      ny = ny + dy[i];
    }
    if (cnt === 5) {
      let prevX = x - dx[i];
      let prevY = y - dy[i];
      if (prevY >= 0 && prevY < 19 && prevX >= 0 && prevX < 19) {
        if (board[prevX][prevY] === color) {
          continue;
        }
      }
      ans = color;
      ansX = x;
      ansY = y;
      return;
    }
  }
  return;
}

for (let i = 0; i < 19; i++) {
  for (let j = 0; j < 19; j++) {
    if (board[i][j] === 0) continue;
    check(i, j, board[i][j]);
  }
}

if (ans === 0) console.log(0);
else console.log(`${ans}\n${ansX + 1} ${ansY + 1}`);

✔ 알고리즘 : 구현(브루트포스)

✔ 현재 칸이 1과 2일때만 check함수를 통해 오목여부를 판단

✔ 답으로 출력해야 하는 좌표가 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알이므로 현재 좌표에서 4개의 방향 (아래, 오른쪽, 오른쪽 아래 대각선, 오른쪽 위 대각선) 을 탐색한다.

❗ cnt가 5일때 바로 답으로 저장하면 육목이 되는 경우도 승리처리가 되기 때문에 cnt가 5인경우 이전 좌표인 prevX,prevY를 현재 칸과 비교하여 다른 경우 만 승리 처리하도록 구현해야 한다.

✔ 난이도 : 백준 기준 실버 2