[코딩테스트/백준 알고리즘] 3085번 : 사탕 게임 (자바, Java 풀이)

문제

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

3085번: 사탕 게임

문제 설명

---

문제 풀이

 

 이 문제를 풀면서 까다로웠던 것은 기준이 되는 칸의 위치에 따라 자리를 바꿀 수 있는 방법의 수가 달라진다는 것이다. 이 경우를 따로 처리해주기가 매우 번거롭기 때문에 이런 경우 쉽게 해결할 수 있는 방법을 소개하겠다.

 

 게임 판(board)의 상하좌우로 테두리를 만들어주면 모든 경우에 대해 자리를 옮기는 방법을 4가지로 통일할 수 있다.

 

자료구조

        int N = Integer.parseInt(br.readLine());	//게임 판의 사이즈
        char[][] board = new char[N + 2][N + 2];	//테두리가 포함된 게임판
        int eat = 1;	//먹을 수 있는 사탕의 최대

 

자리 바꾸기

    /*자리 바꾸기*/
    public static char[][] swap(char[][] board, int x1, int y1, int x2, int y2){
        
        if(board[x1][y1] != board[x2][y2]) {	//두 칸의 사탕 종류가 다르면
            char temp = board[x1][y1];
            board[x1][y1] = board[x2][y2];
            board[x2][y2] = temp;
        }
        return board;
    }

 swap() 메서드는 두 좌표에 있는 사탕의 위치를 바꾸는 메서드다.

 

먹을 수 있는 사탕의 개수 확인

    /*먹을 수 있는 사탕 개수 확인*/
    public static int check(char[][] board) {
        int eat = 1;
        /*가로줄*/
        for(int i = 1; i <= board.length - 2; i++) {
            char prev = board[i][1];
            int count = 1;
            for(int j = 2; j <= board.length - 2; j++) {
                if(prev == board[i][j]) {
                    count++;
                    eat = Math.max(eat, count);
                }
                else {
                    prev = board[i][j];
                    eat = Math.max(eat, count);
                    count = 1;
                }
            }
        }
        
        /*세로줄*/
        for(int i = 1; i <= board.length - 2; i++) {
            char prev = board[1][i];
            int count = 1;
            for(int j = 2;  j <= board.length - 2; j++) {
                if(prev == board[j][i]) {
                    count++;
                    eat = Math.max(eat, count);
                }
                else {
                    prev = board[j][i];
                    eat = Math.max(eat, count);
                    count = 1;
                }
            }
        }
        return eat;
    }

 

메인 함수의 호출문

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                eat = Math.max(eat, check(swap(board, i, j, i - 1, j)));	//왼쪽
                swap(board, i, j, i - 1, j);	//게임판 복구
                eat = Math.max(eat, check(swap(board, i, j, i + 1, j)));	//오른쪽
                swap(board, i, j, i + 1, j);	//게임판 복구
                eat = Math.max(eat, check(swap(board, i, j, i, j - 1)));	//아래
                swap(board, i, j, i, j - 1);	//게임판 복구
                eat = Math.max(eat, check(swap(board, i, j, i, j + 1)));	//위
                swap(board, i, j, i, j + 1);	//게임판 복구
            }
        }

 이차원 배열의 경우 매개변수로 전달될 때 객체 원본을 전달하기 때문에 swap()메서드에 한번 들어갔다 오면 원본 게임판이 훼손된다. 때문에 원봉 상태로 복구 해주는 과정이 필요하다.

---

코드

import java.util.*;
import java.io.*;
class Main {

    /*자리 바꾸기*/
    public static char[][] swap(char[][] board, int x1, int y1, int x2, int y2){
        if(board[x1][y1] != board[x2][y2]) {
            char temp = board[x1][y1];
            board[x1][y1] = board[x2][y2];
            board[x2][y2] = temp;
        }
        return board;
    }

    /*먹을 수 있는 사탕 개수 확인*/
    public static int check(char[][] board) {
        int eat = 1;
        /*가로줄*/
        for(int i = 1; i <= board.length - 2; i++) {
            char prev = board[i][1];
            int count = 1;
            for(int j = 2; j <= board.length - 2; j++) {
                if(prev == board[i][j]) {
                    count++;
                    eat = Math.max(eat, count);
                }
                else {
                    prev = board[i][j];
                    eat = Math.max(eat, count);
                    count = 1;
                }
            }
        }

        for(int i = 1; i <= board.length - 2; i++) {
            char prev = board[1][i];
            int count = 1;
            for(int j = 2;  j <= board.length - 2; j++) {
                if(prev == board[j][i]) {
                    count++;
                    eat = Math.max(eat, count);
                }
                else {
                    prev = board[j][i];
                    eat = Math.max(eat, count);
                    count = 1;
                }
            }
        }
        return eat;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());	//게임 판의 사이즈
        char[][] board = new char[N + 2][N + 2];	//게임판
        int eat = 1;	//먹을 수 있는 사탕의 최대

        /*게임판 제작*/
        for(int i = 1; i <= N; i++) {
            char[] tmp = br.readLine().toCharArray();
            for(int j = 1; j <= N; j++) {
                board[i][j] = tmp[j - 1];
            }
        }

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                eat = Math.max(eat, check(swap(board, i, j, i - 1, j)));	//왼쪽
                swap(board, i, j, i - 1, j);	//게임판 복구
                eat = Math.max(eat, check(swap(board, i, j, i + 1, j)));	//오른쪽
                swap(board, i, j, i + 1, j);	//게임판 복구
                eat = Math.max(eat, check(swap(board, i, j, i, j - 1)));	//아래
                swap(board, i, j, i, j - 1);	//게임판 복구
                eat = Math.max(eat, check(swap(board, i, j, i, j + 1)));	//위
                swap(board, i, j, i, j + 1);	//게임판 복구
            }
        }
        
        System.out.println(eat);
    }
}