CosPro1급 모의고사 - Part.3 함수 작성 - 꽃피우기 (C언어)

Cos Pro 1급 모의고사 - 꽃피우기 에 대한 C언어를 이용한 저의 풀이입니다.

 

목차

• 문제 설명
• 매개변수 설명
• return 값 설명
• 예제
• ***풀이 전략***
• 문제와 답

 

문제 설명

정사각형 크기 격자 모양 정원에 칸마다 핀 꽃 또는 피지 않은 꽃을 심었습니다. 이 정원의 꽃이 모두 피는 데 며칠이 걸리는지 알고 싶습니다. 핀 꽃은 하루가 지나면 앞, 뒤, 양옆 네 방향에 있는 꽃을 피웁니다.

현재 정원의 상태를 담은 2차원 배열 garden, garden의 행 길이 garden_row_len, garden의 열 길이 garden_col_len이 주어졌을 때, 모든 꽃이 피는데 며칠이 걸리는지 return 하도록 solution 함수를 작성해주세요.

 

매개변수 설명

현재 정원의 상태를 담은 2차원 배열 garden, garden의 행 길이 garden_row_len, garden의 열 길이 garden_col_len이 solution 함수의 매개변수로 주어집니다.

• garden_row_len과 garden_col_len은 서로 같으며, 2 이상 100 이하인 자연수입니다.
• 정원 상태를 담은 2차원 배열 garden의 원소는 0 또는 1 입니다.
• 이미 핀 꽃은 1로 아직 피지 않은 꽃은 0으로 표현합니다.
• 정원에 최소 꽃 한 개는 피어 있습니다.

 

return 값 설명

꽃이 모두 피는데 며칠이 걸리는지 return 합니다.

예제

garden	garden_row_len	garden_col_len	return
[[0,0,0], [0,1,0], [0,0,0]]	3	3	2
[[1,1], [1,1]]	2	2	0

 

문제와 답

 

// 다음과 같이 include를 사용할 수 있습니다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
 
int solution(int **garden, int garden_row_len, int garden_col_len) {
    // 여기에 코드를 작성해주세요.
    int answer = 0;
    // 다음날 정원
    int **garden_new = (int**)malloc(sizeof(int*) * garden_row_len);
    for(int i = 0; i < garden_row_len; i++)
        garden_new[i] = (int*)malloc(sizeof(int) * garden_col_len);
    for(int i = 0 ; i < garden_row_len; i++){
        for(int j = 0 ; j < garden_col_len; j++){
            garden_new[i][j] = 0;
        }
    }
            
    while(1)
    {
        // 모두 더한 합을 구해서 꽃이 다 폈는지 확인해보자.
        int no_blossum = 0;
        for(int i = 0 ; i < garden_row_len; i++){
            for(int j = 0 ; j < garden_col_len; j++){
                no_blossum += garden[i][j];
            }
        }
        // 모두 개화했으면 나온다.
        if (no_blossum >= garden_row_len * garden_col_len)
            break;
        else // 아니면 하루 더 묵자
            answer++;
        
        // 개화 규칙
        for(int i = 0 ; i < garden_row_len; i++){
            for(int j = 0 ; j < garden_col_len; j++){
                if (garden[i][j] == 1){
                    garden_new[i][j] = 1;
                    if (i != 0)
                        garden_new[i-1][j] = 1;
                    if (i != garden_row_len-1)
                        garden_new[i+1][j] = 1;
                    if (j != 0)
                        garden_new[i][j-1] = 1;
                    if (j != garden_col_len-1)
                        garden_new[i][j+1] = 1;
                }
            }
        }
        // 다음날 개화 격자
        for(int i = 0 ; i < garden_row_len; i++){
            for(int j = 0 ; j < garden_col_len; j++){
                garden[i][j] = garden_new[i][j];
            }
        }
    }
            
    return answer;
}
 
 
// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다.
int main() {
    int garden1_row_len = 3;
    int garden1_col_len = 3;
    int **garden1 = (int**)malloc(sizeof(int*) * garden1_row_len);
    for(int i = 0; i < garden1_row_len; i++)
        garden1[i] = (int*)malloc(sizeof(int) * garden1_col_len);
 
    garden1[0][0] = 0;
    garden1[0][1] = 0;
    garden1[0][2] = 0;
    garden1[1][0] = 0;
    garden1[1][1] = 1;
    garden1[1][2] = 0;
    garden1[2][0] = 0;
    garden1[2][1] = 0;
    garden1[2][2] = 0;
 
    int ret1 = solution(garden1, garden1_row_len, garden1_col_len);
 
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    printf("solution 함수의 반환 값은 %d 입니다.\n", ret1);
 
    int garden2_row_len = 2;
    int garden2_col_len = 2;
    int **garden2 = (int**)malloc(sizeof(int*) * garden2_row_len);
    for(int i = 0; i < garden2_row_len; i++)
        garden2[i] = (int*)malloc(sizeof(int) * garden2_col_len);
 
    garden2[0][0] = 1;
    garden2[0][1] = 1;
    garden2[1][0] = 1;
    garden2[1][1] = 1;
 
    int ret2 = solution(garden2, garden2_row_len, garden2_col_len);
 
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    printf("solution 함수의 반환 값은 %d 입니다.\n", ret2);
}

 

풀이 전략

꽃 피는 규칙으로부터 그 날의 개화를 계산하기

같은 배열 garden에 놓고 하게 되면 규칙이 복잡해지므로,

어제와 내일의 정원 격자 garden, garden_new로 구분하여

garden을 기준으로 내일의 개화를 내일의 정원 격자 garden_new에 표시하자.

내가 세운 절차는 다음과 같다.

1. 꽃 핀 표시가 1이므로, 모든 격자의 요소를 더해서 꽃 핀 셀 수를 계산한다.
2. 꽃 핀 셀 수와 총 셀 수가 같으면 그만한다. 아니면 하루를 더 세어보자.
3. 개화 규칙은 어제 꽃 핀 주변에 내일 꽃이 핀다는 것이다. 예외 사항으로 벽을 구분한다.
4. 내일 정원 격자 garden_new를 오늘 정원 격자 garden 으로 옮겨 하루가 지났음을 표시한다.

꽃이 피었는지를 먼저 확인하는 이유는 예제와 같이 모두 이미 핀 상태도 있기 때문이다.