[백준]3085번 사탕 게임 - Java

문제

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

3085번: 사탕 게임

 

풀이

완전완전탐색으로 풀었음

2차원 배열을 하나하나씩 돌면서 4방으로 탐색해줌

인접한 사탕이 같은 종류면 다음 방향으로 넘어가고, 다른 종류면 스왑한 다음 solution() 함수를 실행하여 연속한 사탕의 최대 개수 max를 최신화함

 

내 생각에 여기서 포인트는 인접한 다른 종류의 사탕끼리 바꿨으면 solution() 함수를 실행해서 max를 최신화한 후, 바꿨던 사탕을 다시 원래대로 바꿔주어야 하고,

solution() 함수 안에서는 큰 for문 안에서 행검사와 열검사를 같이 해주면 시간복잡도를 조금이나마 줄일 수 있음

 

solution() 함수는 2차원 배열 map[][]에서 현재 인덱스와 다음 인덱스를 비교하면서 count값을 증가시키거나 1로 초기화하면서 최대 count값을 구하는 함수임

 

코드

// 3085번 사탕 게임
// https://www.acmicpc.net/problem/3085

package BAEKJOON;

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

public class Num3085_사탕게임 {
    static int N;
    static char[][] map;
    // 상하좌우
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        map = new char[N][N];


        // 입력
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        int max = Integer.MIN_VALUE;

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

                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];

                    // map 밖이면
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                        continue;
                    }
                    // 인접한 애들이 같으면
                    if (map[r][c] == map[nr][nc]) {
                        continue;
                    }

                    // 인접한 애들이 다르면
                    if (map[r][c] != map[nr][nc]) {
                        // 스왑
                        char temp = map[nr][nc];
                        map[nr][nc] = map[r][c];
                        map[r][c] = temp;

                        // 먹을 수 있는 사탕 개수 세기
                        max = Math.max(max, solution());

                        // 원래대로 돌려놓기
                        temp = map[nr][nc];
                        map[nr][nc] = map[r][c];
                        map[r][c] = temp;
                    }
                }
            }
        }

        System.out.println(max);
    }

    public static int solution() {
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < N; i++) {
            // 행검사
            int count = 1;
            for (int j = 0; j < N - 1; j++) {
                if (map[i][j] == map[i][j + 1]) {
                    count++;
                } else {
                    count = 1;
                }
                max = Math.max(max, count);
            }

            // 열검사
            count = 1;
            for (int j = 0; j < N - 1; j++) {
                if (map[j][i] == map[j + 1][i]) {
                    count++;
                } else {
                    count = 1;
                }
                max = Math.max(max, count);
            }
        }

        return max;
    }
}