[JS][백준]23081_오델로

문제 번호

23081번: 오델로

 

 

알고리즘 분류

• 구현
• 브루트포스 알고리즘

 

문제 풀이

 문제 자체는 어렵지않다. 그냥 시키는 대로 구현만 하면된다. 그런데 검은돌(B)과 검은돌(B)사이에 흰돌(W)만 있어야 하는데 빈공간(.) 다음에 빈공간이 이어지고, 그 뒤에 흰돌(W)가 이어진뒤, 검은돌(B)로 끝나는 경우를 생각하지 못해서 생각보다 오래걸렸다.

 

 문제에서 입력받은 오델로 게임판을 탐색하다가 빈 공간을 발견하면 해당 공간에 검을돌을 놓았을때 몇개의 흰돌을 뒤집을 수 있는지 확인한다.

   let max = 0;
   for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
         if (othello[i][j] === '.') {
            let ret = check(i, j, N, othello);
            if (ret >= max) {
               max = ret;
               candidate.push({
                  y: i,
                  x: j,
                  cnt: ret
               })
            }
         }
      }
   }

 만약 뒤집을 수 있는 흰돌의 갯수가 기존에 뒤집었던 갯수보다 많다면 candidate 배열에 좌표와 함께 추가한다.

 

모든 점에 대한 탐색이 끝났다면 문제에서 주어진 조건에 맞게 candidate배열을 정렬한다.

   candidate.sort((a, b) => {
      let A = a.cnt
      let B = b.cnt
      if (A > B) return -1;
      else if (A < B) return 1;
      else {
         A = a.y;
         B = b.y;
         if (A < B) return -1;
         else if (A > B) return 1;
         else {
            A = a.x;
            B = b.x;
            if (A < B) return -1;
            else if (A > B) return 1;
            return 0;
         }
      }
   })

 

 

전체코드

function main() {
   const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
   const N = +input[0].trim();
   let othello = input.slice(1).map(_ => _.trim().split(''));

   let answer = sol(N, othello);

   return console.log(answer);
}
function sol(N, othello) {
   let answer = ''
   let candidate = [];

   let max = 0;
   for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
         if (othello[i][j] === '.') {
            let ret = check(i, j, N, othello);
            if (ret >= max) {
               max = ret;
               candidate.push({
                  y: i,
                  x: j,
                  cnt: ret
               })
            }
         }
      }
   }   
   candidate.sort((a, b) => {
      let A = a.cnt
      let B = b.cnt
      if (A > B) return -1;
      else if (A < B) return 1;
      else {
         A = a.y;
         B = b.y;
         if (A < B) return -1;
         else if (A > B) return 1;
         else {
            A = a.x;
            B = b.x;
            if (A < B) return -1;
            else if (A > B) return 1;
            return 0;
         }
      }
   })   

   if (max === 0)
      answer = "PASS";
   else {
      answer += candidate[0].x + ' ' + candidate[0].y + '\n' + candidate[0].cnt;
   }

   return answer;
}
function check(y, x, N, othello) {
   let answer = 0;

   // 위
   let cnt = 0;
   for (let i = y; i >= 0; i--) {      
      if(i !== y && othello[i][x] === '.'){
         break;
      }
      if (othello[i][x] === 'W')
         cnt++;
      else if (othello[i][x] === 'B') {
         answer += cnt;
         break;
      }
   }
   // 오른 대각 위
   cnt = 0;
   for (let i = 0; i < N; i++) {
      let [row, col] = [y, x];
      row -= i;
      col += i;
      if (row < 0 || col >= N) break;
      if(row !== y && col !== x && othello[row][col] === '.')  break;
      if (othello[row][col] === 'W')
         cnt++;
      else if (othello[row][col] === 'B') {
         answer += cnt;
         break;
      }

   }
   //오른쪽
   cnt = 0;
   for (let i = x; i < N; i++) {      
      if(i!==x && othello[y][i] === '.')  break;
      if (othello[y][i] === 'W')
         cnt++;
      else if (othello[y][i] === 'B') {
         answer += cnt;
         break;
      }

   }
   // 오른 대각 아래.
   cnt = 0;
   for (let i = 0; i < N; i++) {
      let [row, col] = [y, x];
      row += i;
      col += i;
      if (row >= N || col >= N) break;      
      if(row !== y && col !== x && othello[row][col] === '.')  break;
      if (othello[row][col] === 'W')
         cnt++;
      else if (othello[row][col] === 'B') {
         answer += cnt;
         break;
      }
   }
   // 아래
   cnt = 0;
   for (let i = y; i < N; i++) {      
      if(i !==y && othello[i][x] === '.')  break;
      if (othello[i][x] === 'W')
         cnt++;
      else if (othello[i][x] === 'B') {
         answer += cnt;
         break;
      }
   }
   // 왼쪽 대각 아래.
   cnt = 0;
   for (let i = 0; i < N; i++) {
      let [row, col] = [y, x];
      row += i;
      col -= i;
      if (row >= N || col < 0) break;      
      if(row !== y && col !== x && othello[row][col] === '.')  break;
      if (othello[row][col] === 'W')
         cnt++;
      else if (othello[row][col] === 'B') {
         answer += cnt;
         break;
      }
   }
   // 왼쪽
   cnt = 0;
   for (let i = x; i >= 0; i--) {      
      if(i!==x && othello[y][i] === '.')  break;
      if (othello[y][i] === 'W')
         cnt++;
      else if (othello[y][i] === 'B') {
         answer += cnt;
         break;
      }
   }
   // 왼쪽 대각 위.
   cnt = 0;
   for (let i = 0; i < N; i++) {
      let [row, col] = [y, x];
      row -= i;
      col -= i;
      if (row < 0 || col < 0) break;      
      if(row !==y && col !==x && othello[row][col] === '.')  break;
      if (othello[row][col] === 'W')
         cnt++;
      else if (othello[row][col] === 'B') {
         answer += cnt;
         break;
      }
   }

   return answer;
}
main();

특이사항

 

구현은 .... 싫다 ..........