[Programmers] Cos Pro 1급 C 모의고사 - 꽃 피우기

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

현재 정원의 상태를 담은 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

예제 설명

예제 #1
첫 날 정원은 아래와 같습니다.

1일이 지난 정원의 상태는 아래와 같습니다.

2일이 지난 정원의 상태는 아래와 같습니다.

따라서, 2일이 지나면 정원의 모든 꽃이 핍니다.

예제 #2
첫 날 화단의 상태는 아래와 같습니다.

따라서, 0일이 지나면 정원의 모든 꽃이 핍니다.

 

---

COS Pro 시험문제는 아래와 같이 적절한 답을 반환하도록 solution 함수를 구현해야 한다.

Flower 구조체를 만들어 q 포인터를 통해 큐의 가장 앞 노드, 말단 노드를 지정하여 구현하였다.

bfs 돌려서 방문 체크하고, 꽃이 피어있는 곳만 queue에 넣어주면서 모든 꽃이 필 때까지 반복한다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct Flower {
	int x, y, day;
} Flower;

Flower *q;
int front;
int rear;

void enqueue(int size, Flower data){
    q[rear] = data;
    rear++;
    rear = rear % size;
}

void dequeue(int size) {
	front++;
	front = front % size;
}

int solution(int **garden, int garden_row_len, int garden_col_len) {
    int answer = 0;
    int dir[4][4] = { {0,1},{0,-1},{1,0},{-1,0}};
    
    int size = garden_row_len * garden_col_len + 1;
    q = (Flower *) malloc(sizeof(Flower) * size);
    front = 0;
    rear = 0;
    
    for(int i=0; i<garden_row_len; i++){
        for(int j=0; j<garden_col_len; j++){
            if(garden[i][j] == 1) {
                Flower flower = {i, j, 0};
                enqueue(size, flower);
            }
        }
    }
    
    while(front != rear){
        Flower flower = q[front];
        dequeue(size);
        
        for(int i=0; i<4; i++){
            int nx = flower.x + dir[i][0];
            int ny = flower.y + dir[i][1];
            int next_day = flower.day + 1;

    		if((0 <= nx && nx < garden_row_len && 0 <= ny && ny < garden_col_len) && !garden[nx][ny]) {
    			garden[nx][ny] = 1;
    			answer = next_day;
    			Flower flower = {nx, ny, next_day};
    			enqueue(size, flower);
    		} 
        }
    }
    
    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);
}

 

[출처]

https://school.programmers.co.kr/learn/courses/11115/lessons/70760