[JAVA][백준 3085] 사탕 게임

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

문제

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

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

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

입력

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

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

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

출력

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

 

---

 

풀이

딱히 무슨 방법이 있는 것 같진 않고 그냥 문제에서 시키는 대로 하면

1. 한칸한칸 보면서 위, 아래, 왼쪽, 오른쪽과 색이 다른지 확인한다.

2 - 1. 4방향 모두 색이 같다면 continue
2 - 2. 다르다면 현재 보고있는 사탕과 다른 부분의 사탕과 자리를 바꾼 후 연속된 사탕의 개수를 세고 그 값이 최대값이라면 갱신한다.

어차피 최솟값을 구하는게 아니라 최댓값을 구하는 것이기때문에 중간에 skip할수도 없고 그냥 완전탐색으로 풀면 되는 문제이다.

 

처음에 잘 푼 것 같은데 계속 테스트케이스와 답이 달라 출력해보던 중 문제 이해를 잘 못 했다는 것을 알게됐다.
나는 bfs를 이용해서 모든 연속된 사탕의 수를 세고 있었는데

문제를 다시 보니 가장 긴 연속된 부분(행 또는 열) 만 보는 것이었다....

너무 어렵게 풀고 있었다...

 

↓↓ 아래는 어렵게 bfs로 모든 사탕개수 세고 있었던 방법.... ↓↓

어렵게 풀던 방법

package S_3085;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    private static int tc;
    private static char[][] candies;
    private static int[][] d = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int answer;

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

        tc = Integer.parseInt(br.readLine());
        candies = new char[tc][tc];

        getCandies();

        for (int r = 0; r < tc; r++) {
            for (int c = 0; c < tc; c++) {
                // 현재 위치
                char now = candies[r][c];

                for (int i = 0; i < 4; i++) {
                    // 비교할 위치
                    int nr = r + d[i][0];
                    int nc = c + d[i][1];

                    // 범위 안에 있을때
                    if (nr >= 0 && nc >= 0 && nr < tc && nc < tc) {
                        // 현재사탕와 비교했을 때 다르다면
                        char side = candies[nr][nc];
                        if (now != side) {
                            // 자리를 바꾼 후
                            candies[r][c] = side;
                            candies[nr][nc] = now;

                            // 연속된 사탕의 수 세기
                            answer = Math.max(answer, count());

                            // 원래 자리로 복구
                            candies[r][c] = now;
                            candies[nr][nc] = side;
                        }
                    }
                }
            }
        }

        System.out.println(answer);
    }

    private static void getCandies() throws IOException {
        for (int i = 0; i < tc; i++) {
            char[] cArr = br.readLine().toCharArray();
            for (int j = 0; j < tc; j++) {
                candies[i][j] = cArr[j];
            }
        }
    }

    private static int count() {
        boolean[][] visited = new boolean[tc][tc];
        int maxCount = 0;

        for (int i = 0; i < tc; i++) {
            for (int j = 0; j < tc; j++) {
                if (!visited[i][j]) {
                    maxCount = Math.max(maxCount, bfs(i, j, visited));
                }
            }
        }

        return maxCount;
    }

    private static int bfs(int startX, int startY, boolean[][] visited) {
        Queue<int[]> q = new LinkedList<>();
        char targetChar = candies[startX][startY];
        int count = 0;

        q.add(new int[]{startX, startY});
        visited[startX][startY] = true;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int x = current[0];
            int y = current[1];
            count++;

            for (int dir = 0; dir < 4; dir++) {
                int newX = x + d[dir][0];
                int newY = y + d[dir][1];

                if (newX >= 0 && newY >= 0 && newX < tc && newY < tc && !visited[newX][newY] && candies[newX][newY] == targetChar) {
                    q.add(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
        }

        return count;
    }
}

 

그래서 다시 올바른 방법으로 푼 결과 성공...

package S_3085;

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

public class Main {
    private static int tc;
    private static char[][] candies;
    private static int[][] d = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int answer;

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

        tc = Integer.parseInt(br.readLine());
        candies = new char[tc][tc];

        getCandies();

        for (int r = 0; r < tc; r++) {
            for (int c = 0; c < tc; c++) {
                // 현재 위치
                char now = candies[r][c];

                for (int i = 0; i < 4; i++) {
                    // 비교할 위치
                    int nr = r + d[i][0];
                    int nc = c + d[i][1];

                    // 범위 안에 있을때
                    if (nr >= 0 && nc >= 0 && nr < tc && nc < tc) {
                        // 현재사탕와 비교했을 때 다르다면
                        char side = candies[nr][nc];
                        if (now != side) {
                            // 자리를 바꾼 후
                            candies[r][c] = side;
                            candies[nr][nc] = now;

                            // 연속된 사탕의 수 세기
                            answer = Math.max(answer, count());

                            // 원래 자리로 복구
                            candies[r][c] = now;
                            candies[nr][nc] = side;
                        }
                    }
                }
            }
        }

        System.out.println(answer);
    }

    private static void getCandies() throws IOException {
        for (int i = 0; i < tc; i++) {
            char[] cArr = br.readLine().toCharArray();
            for (int j = 0; j < tc; j++) {
                candies[i][j] = cArr[j];
            }
        }
    }

    private static int count() {
        int maxCount = 0;

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

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

        return maxCount;
    }
}