BOJ) 사탕 게임

사탕 게임

3085번: 사탕 게임

풀이

 

NxN 크기의 보드에 사탕이 가득 채워져 있다.

사탕의 색이 다른 인접한 두 칸을 골라서 서로 교환한다.

이 때, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 or 열)을 고른 다음 그 사탕을 다 먹는다.

사탕을 먹을 수 있는 최대 갯수를 구하는 문제다.

 

알고리즘을 활용한다기 보다 구현에 가까운 문제라고 느꼈고, 간단하게 풀 수 있었다.

맵을 돌면서, 상하좌우에 있는 사탕과 바꾸고,

상/하로 바꿨을 경우에는 해당 행을 검색하고, 좌/우로 바꿨을 경우에는 해당 열을 검색했다.

그리고, 현재 위치에서 바꾸지 않고 다른 위치에서 바꿨을 경우도 찾기 위해서, 사탕을 바꾸기 전에 행과열에 최대 인접 사탕의 수를 구했다.

 

이 로직을 이용하면 하나의 좌표에 대해 총 6번의 검사를 한다.

해당 위치의 행렬의 사탕을 바꾸지 않은 경우에 ~> 행과 열을 검사

행의 사탕을 바꾼 경우에 ~> 열을 검사

열의 사탕을 바꾼 경우에 ~> 행을 검사

 

 

코드

 

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

public class Main {
    private final static int[] dPos = {1,-1};
    private static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        char[][] map = new char[n][n];

        for(int y=0; y<n; y++) {
            map[y] = br.readLine().toCharArray();
        }
        br.close();

        solution(map);
    }

    private static void solution(char[][] map) {
        int answer =0;
        for(int y=0; y<n; y++) {
            for(int x=0; x<n; x++) {
                answer = Math.max(answer, Math.max(findVertical(x, map), findHorizontal(y, map)));
                for(int i=0; i<2; i++) {
                    int nx = x+dPos[i];
                    int ny = y+dPos[i];
                    if(isInArea(nx,y)) {
                        map = swapX(x, nx, y, map);
                        answer = Math.max(answer, findVertical(x, map));
                        map = swapX(x, nx, y, map);
                    }
                    if(isInArea(x,ny)) {
                        map = swapY(y, ny, x, map);
                        answer = Math.max(answer, findHorizontal(y,map));
                        map = swapY(y, ny, x, map);
                    }
                }
            }
        }
        System.out.println(answer);
    }

    private static boolean isInArea(int x, int y) {
        return x>=0 && y>=0 && x<n && y<n;
    }

    private static char[][] swapX(int x, int nx, int y, char[][] map) {
        char tmp = map[y][x];
        map[y][x] = map[y][nx];
        map[y][nx] = tmp;
        return map;
    }
    private static char[][] swapY(int y, int ny, int x, char[][] map) {
        char tmp = map[y][x];
        map[y][x] = map[ny][x];
        map[ny][x] = tmp;
        return map;
    }

    private static int findVertical(int x, char[][] map) { // 세로 검색
        int result =0;
        int partialSum =1;
        char prev = 'a';

        for(int y=0; y<n; y++) {
            if(prev != map[y][x]) {
                prev = map[y][x];
                partialSum =1;
            } else { partialSum++; }
            result = Math.max(result,partialSum);
        }
        return result;

    }
    private static int findHorizontal(int y, char[][] map) {    // 가로 검색
        int result =0;
        int partialSum =1;
        char prev = 'a';

        for(int x=0; x<n; x++) {
            if(prev != map[y][x]) {
                prev = map[y][x];
                partialSum =1;
            } else { partialSum++; }
            result = Math.max(result,partialSum);
        }
        return result;
    }
}