[BAEKJOON] 3085. 사탕 게임(JAVA)

:D 문제

---

문제

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

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

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

입력

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

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

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

출력

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

Baekjoon

3085번: 사탕 게임

 

:D 풀이 방법

---

나는 먼저, 현재 사탕을 기준으로 인접한 사탕을 고르기 위해 4방 탐색을 진행하였다. 그리고 탐색할 수 있는 사탕이라면, 현재 사탕과 swap한 후에 모두 같은 색으로 이루어진 행 또는 열을 찾아 카운팅을 진행하였다. 그리고 swap한 사탕들을 다시 한번 swap하여 원래대로 돌려주는 작업을 반복하였다.

 

 

:D 작성 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution3085H {
    static char[][] board;
    // 상 하 좌 우
    static int[][] deltaXY = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int N, maxCount;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        board = new char[N][N];
        maxCount = 0;

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            board[i] = line.toCharArray();
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                search(i, j);
            }
        }
        System.out.print(maxCount);
    }

    // 4방 탐색 - 인접한 사탕의 색이 다르다면 swap
    private static void search(int x, int y) {

        for (int i = 0; i < 4; i++) {

            int nx = x + deltaXY[i][0];
            int ny = y + deltaXY[i][1];

            // 범위를 벗어났거나 인접한 곳에 사탕 색이 같다면, continue
            if (!isIn(nx, ny) || board[x][y] == board[nx][ny]) continue;

            // swap
            swapCandy(x, y, nx, ny);
            findMaxColor();
            swapCandy(x, y, nx, ny);
        }
    }

    // 범위 확인
    private static boolean isIn(int nx, int ny) {
        return nx >= 0 && ny >= 0 && nx < N && ny < N;
    }

    // 인접한 사탕 교체
    private static void swapCandy(int x, int y, int nx, int ny) {
        char tmp = board[x][y];
        board[x][y] = board[nx][ny];
        board[nx][ny] = tmp;
    }

    // 가장 긴 연속된 부분 찾기(행/열)
    private static void findMaxColor() {

        for (int i = 0; i < N; i++) {

            if (maxCount == N) return;

            int rowCnt = 1;
            for (int j = 1; j < N; j++) {
                rowCnt = board[i][j - 1] != board[i][j] ? 1 : rowCnt + 1;
                maxCount = Math.max(rowCnt, maxCount);
            }

            int columnCnt = 1;
            for (int j = 1; j < N; j++) {
                columnCnt = board[j - 1][i] != board[j][i] ? 1 : columnCnt + 1;
                maxCount = Math.max(columnCnt, maxCount);
            }
        }
    }
}