문제 설명

N×N 크기의 보드에 서로 다른 색의 사탕이 놓여 있다.
상근이는 다음과 같은 행동을 한다.

1. 서로 인접한 두 칸을 선택
2. 두 칸의 사탕을 서로 교환
3. 같은 색으로 이루어진 가장 긴 연속 부분(행 또는 열)을 선택
4. 그 길이를 구한다

이때, 한 번의 교환으로 만들 수 있는
가장 긴 연속 사탕 개수를 구하는 문제이다.

---

입력

첫째 줄

N

보드 크기

다음 N줄

사탕 정보

• C, P, Z, Y 중 하나

조건

3 ≤ N ≤ 50

---

출력

한 번의 교환으로 얻을 수 있는
최대 연속 사탕 개수

---

입력 예시

3
CCP
CCP
PPC

출력 예시

3

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

모든 가능한 교환을 시도하고
각 경우마다 최대 연속 길이를 계산한다

---

해결 흐름

1. 모든 칸을 순회
2. 오른쪽, 아래 방향으로만 교환 시도
3. 교환 후 최대 길이 계산
4. 다시 원상복구
5. 최대값 갱신

---

강의 풀이

강의에서는 다음 구조로 문제를 해결했다.

1. 사탕 교환

swapCandy(map, i, j, i, j + 1);

---

2. 점수 계산 함수

행과 열을 각각 검사하여
가장 긴 연속 길이를 구한다.

calcScore(map)

---

코드

import java.util.Scanner;

class Main
{
    public static int calcScore(char[][] map) {
        int N = map.length;
        int maxScore = 0;

        for (int r = 0; r < N; r++) {
            int scr = 1;
            for (int c = 1; c < N; c++) {
                if (map[r][c] == map[r][c - 1]) scr++;
                else {
                    maxScore = Math.max(maxScore, scr);
                    scr = 1;
                }
            }
            maxScore = Math.max(maxScore, scr);
        }

        for (int c = 0; c < N; c++) {
            int scr = 1;
            for (int r = 1; r < N; r++) {
                if (map[r][c] == map[r - 1][c]) scr++;
                else {
                    maxScore = Math.max(maxScore, scr);
                    scr = 1;
                }
            }
            maxScore = Math.max(maxScore, scr);
        }

        return maxScore;
    }

    public static void swapCandy(char[][] map, int r1, int c1, int r2, int c2) {
        char tmp = map[r1][c1];
        map[r1][c1] = map[r2][c2];
        map[r2][c2] = tmp;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        char[][] map = new char[N][N];

        for (int i = 0; i < N; i++)
            map[i] = sc.next().toCharArray();

        int ans = 0;

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

                if (j + 1 < N) {
                    swapCandy(map, i, j, i, j + 1);
                    ans = Math.max(ans, calcScore(map));
                    swapCandy(map, i, j, i, j + 1);
                }

                if (i + 1 < N) {
                    swapCandy(map, i, j, i + 1, j);
                    ans = Math.max(ans, calcScore(map));
                    swapCandy(map, i, j, i + 1, j);
                }
            }

        System.out.println(ans);
    }
}

---

내가 작성한 코드 문제점

내 코드는 다음과 같은 방식으로 접근했다.

• 현재 상태에서 바로 최대 연속 길이를 계산
• 주변 값과 비교하여 가능성을 판단

하지만 이 방식에는 중요한 문제가 있다.

---

1. 교환을 실제로 하지 않음

문제는

사탕을 실제로 교환한 후
결과를 확인해야 한다

인데, 내 코드는

교환 가능성만 보고 계산

하고 있다.

즉, 실제 상태를 바꾸지 않고
가정으로 처리하려고 해서 로직이 복잡해졌다.

---

2. 조건 분기가 너무 많음

코드에서

if(j + 1 < N && ...)
if(i != 0 && ...)
if(i+1 < N && ...)

처럼 많은 조건이 들어가면서

가독성이 떨어지고
버그 가능성이 높아짐

---

3. 문제 핵심을 놓침

이 문제의 핵심은

모든 경우를 시도
→ 계산

인데, 내 코드는

특정 경우만 예측

하려고 했다.

---

두 풀이 방식 비교

방식	특징
내 풀이	조건으로 가능성 판단
강의 풀이	실제 swap 후 전체 탐색

강의 방식이

더 단순하고 안정적

이다.

---

시간 복잡도

강의 코드 기준

O(N³)

설명

• N²개의 위치
• 각 위치마다 점수 계산 O(N²)

하지만

N ≤ 50

이므로

50³ = 125000

충분히 빠르다.

---

핵심 개념

1. 브루트포스

모든 경우를 직접 시도하는 방식

가능한 모든 swap

---

2. 상태 변경 후 계산

swap → 계산 → 원상복구

이 패턴은 매우 중요하다.

---

3. 행/열 분리 계산

행과 열을 따로 검사해야 한다.

---

정리

이 문제는 복잡한 조건을 생각하기보다
단순하게 모든 경우를 직접 시도하는 것이 핵심이었다.

처음에는 조건을 통해 최적의 경우를 찾으려 했지만,
오히려 코드가 복잡해지고 오류 가능성이 높아졌다.

강의 풀이처럼

swap → 전체 검사 → 복구

방식이 훨씬 직관적이고 안정적인 해결 방법이었다.

이 문제를 통해

브루트포스는 단순하게 구현하는 것이 중요하다

는 점을 배울 수 있었다.