[백준 / C언어] Day46. 사탕 게임 (3085)

2024. 07. 19 - 코딩테스트 스터디 Day46

 
 

01. 문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
 
 

02. 입력

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

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

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

 
 

03. 출력

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

04-1. 예제 입력 1

3
CCP
CCP
PPC

 
 

04-2. 예제 출력 1

3

 
 

05-1. 예제 입력 2

4
PPPP
CYZY
CCPY
PPCC

 
 

05-2. 예제 출력 2

4

 
 

06-1. 예제 입력 3

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

 
 

06-2. 예제 출력 3

4

 
 

07. 힌트

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
 
 

08. 풀이 및 답

#include <stdio.h>

int count_candies(char arr[50][50], int n) {
    int max_candies = 0;
    
    // 행에서 가장 긴 연속 부분 계산
    for (int i = 0; i < n; i++) {
        int count = 1;
        
        for (int j = 1; j < n; j++) {
            if (arr[i][j] == arr[i][j - 1]) {
                count++;
                if (max_candies < count) {
                    max_candies = count;
                }
            }
            else {
                count = 1;
            }
        }
    }
    
    // 열에서 가장 긴 연속 부분 계산
    for (int j = 0; j < n; j++) {
        int count = 1;
        
        for (int i = 1; i < n; i++) {
            if (arr[i][j] == arr[i - 1][j]) {
                count++;
                if (max_candies < count) {
                    max_candies = count;
                }
            }
            else {
                count = 1;
            }
        }
    }
    
    return max_candies;
}

int main() {
    int n;
    char arr[50][50];
    
    scanf("%d", &n);
    
    // 사탕 색상 입력받기
    for (int i = 0; i < n; i++) {
        scanf("%s", arr[i]);
    }
    
    int max_candies = 0; // 최대 연속 사탕 개수
    int count = 0; // 연속 사탕 개수
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 오른쪽과 교환
            if (j + 1 < n) {
                char temp = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = temp;
                
                count = count_candies(arr, n);
                
                if (max_candies < count) {
                    max_candies = count;
                }
                
                temp = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = temp;
            }
            
            // 아래쪽과 교환
            if (i + 1 < n) {
                char temp = arr[i][j];
                arr[i][j] = arr[i + 1][j];
                arr[i + 1][j] = temp;
                
                count = count_candies(arr, n);
                
                if (max_candies < count) {
                    max_candies = count;
                }
                
                temp = arr[i][j];
                arr[i][j] = arr[i + 1][j];
                arr[i + 1][j] = temp;
            }
        }
    }
    
    printf("%d\n", max_candies);
    
    return 0;
}

 
우선 이 문제는 인접한 사탕 두 개를 서로 바꿔보고, 연속된 사탕의 개수를 count 한 뒤, 다시 사탕의 배열을 원래대로 돌려놓는 과정으로 진행된다.
인접한 사탕은 위, 아래, 왼쪽, 오른쪽 모두를 교환해볼 필요 없이, 기준 사탕에서 오른쪽, 아래쪽으로만 교환해 보면 된다.

위 그림처럼 아래와 오른쪽으로만 교환을 하다보면 모든 인접한 사탕을 교환할 수 있게 된다
 
 
코드가 길기 때문에 나눠서 설명을 적도록 하겠다.
 
01-1. [main] 인접한 사탕 두 개 교환하기 - 오른쪽

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 오른쪽과 교환
            if (j + 1 < n) {
                char temp = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = temp;
                
                count = count_candies(arr, n);
                
                if (max_candies < count) {
                    max_candies = count;
                }
                
                temp = arr[i][j];
                arr[i][j] = arr[i][j + 1];
                arr[i][j + 1] = temp;
            }

j의 다음 칸이 n보다 작다면 arr[i][j]과 arr[i][j + 1]의 값을 교환한다. 기준점과 그 오른쪽 칸을 교환하는 것이다.
그다음, 행에서 가장 긴 연속 부분을 계산하여 count 변수에 저장한다.
지금 상태에서 구한 연속된 사탕 개수(count)가 지금까지 구한 최대 연속 사탕의 개수(max_candies)보다 크다면 max_candies에 count 값을 저장한다.
그런 다음, 위에서 교환한 두 칸을 다시 교환하여, 원래의 상태로 복구한다.
 
01-2. [main] 인접한 사탕 두 개 교환하기 - 아래쪽

            if (i + 1 < n) {
                char temp = arr[i][j];
                arr[i][j] = arr[i + 1][j];
                arr[i + 1][j] = temp;
                
                count = count_candies(arr, n);
                
                if (max_candies < count) {
                    max_candies = count;
                }
                
                temp = arr[i][j];
                arr[i][j] = arr[i + 1][j];
                arr[i + 1][j] = temp;
            }

아래쪽 칸과 교환하는 건 j가 아닌 i를 건든다는 점 말고는 특별히 다른 점이 없다.
 
02-1. [count_candies] 가장 긴 연속 부분 계산하기 - 행

int count_candies(char arr[50][50], int n) {
    int max_candies = 0;
    
    // 행에서 가장 긴 연속 부분 계산
    for (int i = 0; i < n; i++) {
        int count = 1;
        
        for (int j = 1; j < n; j++) {
            if (arr[i][j] == arr[i][j - 1]) {
                count++;
                if (max_candies < count) {
                    max_candies = count;
                }
            }
            else {
                count = 1;
            }
        }
    }

행에서 가장 긴 연속 부분을 계산하는 방식은 위와 같다.
count를 1로 설정해두고 j가 1부터 n이 되기 전까지 증가하면서 arr[i][j]와 arr[i][j - 1]가 같은 색상인지 확인하고, 같은 색상이라면 count에 +1을 한다. 만약 max_candies 안에 들어있는 값보다 count가 더 크다면 count 값으로 갱신한다.
 
02-2. [count_candies] 가장 긴 연속 부분 계산하기 - 열

    // 열에서 가장 긴 연속 부분 계산
    for (int j = 0; j < n; j++) {
        int count = 1;
        
        for (int i = 1; i < n; i++) {
            if (arr[i][j] == arr[i - 1][j]) {
                count++;
                if (max_candies < count) {
                    max_candies = count;
                }
            }
            else {
                count = 1;
            }
        }
    }
    
    return max_candies;

열에서 가장 긴 연속 부분을 계산하는 방법은 arr[i][j]와 arr[i - 1][j]를 비교한다는 점 말고는 다른 점이 없다.
 
마지막에 가장 긴 연속 부분의 길이인 max_candies를 리턴해주면 된다.
 
 

정답!
 

---

너무 어려워서 오늘 문제는 여러 게시글의 도움을 받아 풀었다...