[BOJ] 3085번 : 사탕 게임

백준 3085번 : 사탕 게임

🔗 문제 링크

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

3085번: 사탕 게임

 

 

---

💬 문제

전형적인  브루트포스(완전 탐색, Brute Force)  문제다. 그렇지만 코드를 짜는 것은 결코 쉽지 않은 문제다.

 

1. 가로 N개, 세로 N개의 사탕이 주어진다.
   
   
2. 이 중에서 사탕의 색이 서로 다른 인접한 사탕을 고르고, 두 사탕의 자리를 바꾼다.
   
   
3. 이제 모두 같은 색으로 이루어진 가장 긴 1줄(가로 or 세로)을 고른 다음, 그 사탕을 모두 먹는다.
   이때 가장 많이 먹을 수 있는 사탕의 개수를 구한다.
   
   

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 N이 주어지고, 그 다음줄부터는 가로 N, 세로N 길이의 사탕이 주어진다. 사탕의 종류는 빨간색 C, 파란색 P, 초록색 Z, 노란색 Y로 구성되어 있다.

줄바꿈으로 잘라 N과 사탕을 분리해주고, 사탕은 2차원 배열로 잘라준다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

🔑 풀이

• 가로, 세로 길이인 N과 사탕 board를 분리해준다.
  
  
• board에서 이동하면서 서로 다른 색이 인접해 있는지 찾아야 한다.
  
  - 그러기 위해 상하좌우의 좌표를 살펴보기 위해 steps 배열을 만들어 준다
  
  - 새로운 좌표는 nx, ny로 설정해주고, 이 좌표가 N x N 보드판을 벗어나면 좌표가 없기에 이땐 통과해준다 (continue)
  
  - 만약 현재 사탕색과 인접한 곳의 사탕색이 서로 다르다면 서로 바꿔주고, 그리고 이 경우 사탕을 가장 많이 먹을 수 있는 경우(최댓값)를 구해준다
  
  - 어떤 사탕을 이동했을 때 최댓값을 구할 수 있을지 모르므로, 최댓값을 확인한 후 사탕 위치를 원상복구해준다.
  
  
• 가로(row), 세로(column) 방향으로 이동하면서 인접한 곳에 같은 색깔의 사탕이 있는지 탐색해준다.
  
  - 최소 1개씩은 있으므로, 가로 경우 row_cnt와 세로 경우 col_cnt에 1을 할당해준다.
  
  - 최댓값을 처음에 비교하기 위해 row_max와 col_max에 음의 정수 -1e9를 할당해준다
  
  - 만약 같은 선상의 인접한 곳에 같은 색깔을 사탕이 있다면, 각 cnt를 +1 해주고, 그렇지 않다면 1로 초기화해준다
  
  - 이동을 하면서 세렸던 cnt의 개수와 최댓값 max를 비교해 더 큰 수로 교체해준다
  
  - 다음 줄도 다시 확인해봐야 하므로 cnt는 1로 초기화해준다
  
  
• 이렇게 가로(row)와 세로(column) 방향으로 탐색을 한 뒤, 각 방향의 최댓값을 비교해 최종적으로 가장 큰 경우를 출력해준다.
  
  

// input값 처리
const input = require('fs').readFileSync('/dev/stdin')
  .toString().trim().split('\n');
const N = Number(input[0]);
const board = input.slice(1).map(v => v.split(''));

let maxCount = 0;

// 좌, 우, 상, 하 방향
const steps = [[-1, 0], [1, 0], [0, -1], [0, 1]];

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    for (let k = 0; k < 4; k++) {  // 4개 방향이므로
      let nx = i + steps[k][0];
      let ny = j + steps[k][1];

      // 보드를 벗어난다면
      if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
        continue;
      }
      // 인접한 두 칸의 사탕 색이 다르다면 바꿔주기
      if (board[i][j] !== board[nx][ny]) {
        [board[nx][ny], board[i][j]] = [board[i][j], board[nx][ny]];
        // 최댓값 계산
        maxCount = Math.max(maxCount, count_candy());
        // 원위치
        [board[i][j], board[nx][ny]] = [board[nx][ny], board[i][j]];
      }
    }
  }
}

// 최대 개수 세는 메서드
function count_candy() {
  let [row_cnt, col_cnt, row_max, col_max] = [1, 1, -1e9, -1e9];

  // 행(row) 계산
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N-1; j++) {
      // 동일한 색상이라면
      if (board[i][j] === board[i][j+1]) {
        row_cnt++;
      } else {
        row_cnt = 1;
      }
      row_max = Math.max(row_cnt, row_max);
    }
    row_cnt = 1;
  }

  // 열(column) 계산
  for (let j = 0; j < N; j++) {
    for (let i = 0; i < N-1; i++) {
      // 동일한 색상이라면
      if (board[i][j] === board[i+1][j]) {
        col_cnt++;
      } else {
        col_cnt = 1;
      }
      col_max = Math.max(col_cnt, col_max);
    }
    col_cnt = 1;
  }
  return answer = Math.max(row_max, col_max);
}

console.log(maxCount);

 

시간은 다음과 같이 걸렸다.