[백준] 3085. 사탕 게임

문제 링크

[백준] 3085. 사탕 게임

풀이 과정

위 그림처럼 (0, 0) 위치의 사탕을 먼저 고른 뒤 그 오른쪽에 위치한 (0, 1) 의 사탕을 고르는 방법이나, (0,1) 의 사탕을 먼저 고른 뒤 그 왼쪽에 위치한 (0, 0) 의 사탕을 고르는 방법이나, 같은 사탕을 고른 결과가 나옵니다. 따라서, 네 방향을 다 볼 필요 없이, 오른쪽과 아래 방향만 swap 하는 과정이 필요합니다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (j + 1 < N) {
            swap(i, j, i, j + 1);
            check();
            swap(i, j, i, j + 1);
        }

        if (i + 1 < N) {
            swap(i, j, i + 1, j);
            check();
            swap(i, j, i + 1, j);
        }
    }
}

위 코드는 오른쪽과 아래 각각에 대해 다음 과정을 거칩니다.

1. 먼저 두 사탕의 위치를 바꾸는 swap 메소드를 호출합니다.
2. 먹을 수 있는 최대 사탕의 개수를 파악하는 check 메소드를 호출합니다.
3. 다시 swap 메소드를 호출해, 두 사탕의 위치를 원래대로 돌려 놓습니다.

static void check() {
    for (int i = 0; i < N; i++) {
        int cnt = 1;

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

        max = Math.max(max, cnt);
    }

    for (int j = 0; j < N; j++) {
        int cnt = 1;

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

        max = Math.max(max, cnt);
    }
}

check 메소드 는 이어져있는 사탕의 최대 개수를 구합니다. 먼저, 각 행에 대해 이어져 있는 사탕의 최대 개수를 구한 뒤, 각 열에 대해 반복합니다.

사탕은 이전 위치의 것과 같다면 그 개수를 증가시키고, 다르다면 누적된 개수를 갱신하는 과정을 거칩니다.

코드

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

public class Main {
    static int N;
    static char[][] map;
    static int max = 0;

    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++) map[i] = br.readLine().toCharArray();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (j + 1 < N) {
                    swap(i, j, i, j + 1);
                    check();
                    swap(i, j, i, j + 1);
                }

                if (i + 1 < N) {
                    swap(i, j, i + 1, j);
                    check();
                    swap(i, j, i + 1, j);
                }
            }
        }

        System.out.println(max);
    }

    static void check() {
        for (int i = 0; i < N; i++) {
            int cnt = 1;

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

            max = Math.max(max, cnt);
        }

        for (int j = 0; j < N; j++) {
            int cnt = 1;

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

            max = Math.max(max, cnt);
        }
    }

    static void swap(int x1, int y1, int x2, int y2) {
        char tmp = map[x1][y1];
        map[x1][y1] = map[x2][y2];
        map[x2][y2] = tmp;
    }
}