백준 3085번: 사탕 게임 - javascript

2 분 소요

백준 3085번: 사탕 게임

문제 설명

상근이는 어렸을 적에 “봄보니 (Bomboni)” 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

접근

이번 문제에서는 아주 노가다적인 효율을 고려하지 않은 코드를 짠 것 같다…

먼저 문제 접근은 다음과 같다. 인접한 사탕의 색이 같던 같지 않던 상근이는 사탕 색이 다른 인접한 두 칸을 고른다. 이때 최대 연속 행 또는 열의 길이를 구하라.

그럼 적어도 2개의 함수를 만들어야 한다.

1. 현재 사탕배열에서 최대 길이를 구하는 함수.
1. 인접한 사탕을 스왑하는 모든 경우를 갖고 있는 함수.

둘다 NxN만큼 2중 반복문으로 돌리면 나온다.

그리고 풀고보니 어떤 사람은 0의 경우나 n같은 모서리의 경우에 n+1쪽은 스왑하지 않게 코드를 구현했던데, 그냥 사탕배열을 감싸는 임의의 경계값 X를 따로 두면 0부터 N까지 다른 조건 없이 원툴로 갈 수 있다.

최대 길이를 구하는 함수

현재 배열에서 최대 길이를 구하려면 행과 열 2가지의 경우를 전부 고려해야한다.
행은 해당 행에서 오른쪽으로 가면서 연속되는지를 체크해야되고,
열은 해당 열에서 아래로 내려가면서 연속되는지를 체크한다.

먼저 행의 경우 현재 사탕의 색을 저장하고 다음으로 넘어간다.
다음 사탕의 색이 같으면 카운터를 올리고 max비교를 해서 max값을 변경한다.
사탕의 색이 다르면 현재 사탕의 색으로 다시 저장하고 카운터를 1로 초기화한다.
이 행위를 2중 반복문에서 arr[i][j]순으로 하나, arr[j][i]순으로 하나를 행해주면 각각 행과 열에 대한 최대 길이가 나올것이고 최종적으로 그 둘의 최대값 중 제일 큰 값을 반환해준다.

인접한 사탕을 모두 스왑하는 함수

이제 반복문을 돌면서 우리는 현재 사탕의 상하좌우의 사탕들고 한번씩 스왑을 해봐야된다.
뭐 스왑은

tmp = a;
a = b;
b = tmp;

의 순으로 하면되고, 이를 i행j열 기준으로 i-1과 i+1과 j-1과 j+1인 자료와 스왑을 한번씩 해주면서 위에서 만든 최대길이를 구하는 함수로 최대값을 반환 받는다.
그리고 매 최대값의 반환마다 현재 최대값과 비교하여 최대값의 갱신을 유지한다.
반복문이 n까지 끝나면 현재 최대값을 반환해주면 끝이다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let arr = [];
  let n = input[0]*1;
  let tmp = new Array(n+2).fill('X');
  //--------입력받을 사탕 주위에 'X'를 채워주는 과정----------//
  arr.push(tmp);
  input.reduce((acc,cur)=>{
    cur = 'X'+cur+'X';
    arr.push(cur.split(''));
  });
  arr.push(tmp);
  //--------입력받을 사탕 주위에 'X'를 채워주는 과정----------//
  console.log(candy_swap(n, arr));
  
  process.exit();
});

let candy_swap = function(n, arr){
  let max_result = counter(n, arr);
  for(let i=1;i<=n;i++){
    for(let j=1;j<=n;j++){
      let tmp = arr[i][j];
      arr[i][j] = arr[i-1][j];
      arr[i-1][j] = tmp;
      max_result = Math.max(max_result, counter(n, arr));
      arr[i-1][j] = arr[i][j];
      arr[i][j] = tmp;

      arr[i][j] = arr[i+1][j];
      arr[i+1][j] = tmp;
      max_result = Math.max(max_result, counter(n, arr));
      arr[i+1][j] = arr[i][j];
      arr[i][j] = tmp;

      arr[i][j] = arr[i][j+1];
      arr[i][j+1] = tmp;
      max_result = Math.max(max_result, counter(n, arr));
      arr[i][j+1] = arr[i][j];
      arr[i][j] = tmp;

      arr[i][j] = arr[i][j-1];
      arr[i][j-1] = tmp;
      max_result = Math.max(max_result, counter(n, arr));
      arr[i][j-1] = arr[i][j];
      arr[i][j] = tmp;
    }
  }
  return max_result;
}

let counter = function(n, arr){
  let max_result = 0;
  for(let i=1;i<=n;i++){    
    let cnt1 =1,cnt2=1,max1=1,max2=1;
    let cur1=arr[0][0],cur2=arr[0][0];
    for(let j=1;j<=n;j++){
      if(cur1==arr[i][j]){
        cnt1++;
        max1 = Math.max(max1, cnt1);
      }else{
        cur1 = arr[i][j];
        cnt1 = 1;
      }
      if(cur2==arr[j][i]){
        cnt2++;
        max2 = Math.max(max2, cnt2);
      }else{
        cur2 = arr[j][i];
        cnt2 = 1;
      }
    }    
    max_result = Math.max(max_result, max1, max2);
  }
  return max_result;
}

Twitter Facebook LinkedIn

ryeon

백준 3085번: 사탕 게임 - javascript