[C++] 프로그래머스 COS Pro 1급 꽃피우기

https://programmers.co.kr/learn/courses/11114/lessons/70743

COS Pro 1급 C++ 모의고사 - 꽃피우기

 

1. 서론

 

BFS 문제인데 그냥 BFS라고 하기도 뭐한? BFS풍의 문제? 문제는 쉬운데 너무 쉽게 생각해서 30분이나 잡아먹음 ㅎ

 

2. 문제 풀이

 

정사각형, 즉 가로와 세로의 길이가 동일한 2차원 배열이 주어진다.

주어진 배열은 0과 1로 나누어져 있는데 이 배열을 정원으로 보고 0인 곳은 꽃이 안 핀곳, 1인 곳은 꽃이 핀 곳으로 간주한다.

꽃이 핀 곳의 상하좌우에는 다음날 꽃이 피게 된다. 이 과정을 계속 반복했을 때 며칠 째에 정원에 모든 꽃이 피는가를 구하는 문제이다.

 

 

 

 

논리는 정말 간단하다. 2차원 배열을 돌면서 0인지 1인지 봐주고 1이면 주변의 상하좌우를 0으로 만들면 된다.

여기서 신경써줘야 할 점은 상하좌우를 돌 때 배열의 범위를 벗어나면 안 된다는 것.

 

그리고 내가 간과했던 점은 그냥 원래 주어진 배열에 바로 0을 1로 바꾸어 버렸는데 그럼 바뀐 1의 주변도 같은 날에 0이 1로 바뀌게 되어 버리기 때문에 답이 이상하게 나온다. 그래서 난 배열을 하나 더 만들어서 그 배열을 tmp 삼아 원래의 배열을 복사하고 tmp 배열에 값이 바뀌게 했다. 그러면 원래의 배열의 값은 바뀌지 않기 때문에 위에서 일어났던 문제를 해결할 수 있게 된다.

 

 

 

 

3. 코드 설명

 

// 다음과 같이 include를 사용할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool check(vector<vector<int>> garden)
{
    for (int i = 0; i < garden.size(); i++)
        for (int j = 0; j < garden[i].size(); j++)
            if (garden[i][j] == 0) return false;
    return true;
}

int solution(vector<vector<int>> garden) {
    // 여기에 코드를 작성해주세요.
    int answer = 0, i, j, k, s = garden.size(), f = 0;
    int dx[4] = {0, -1, 1, 0}, dy[4] = {1, 0, 0, -1};
    
    while(1)
    {
        if(check(garden)) break;
        
        vector<vector<int>> t = garden;
        
        for (i = 0; i < s; i++)
        {
            for (j = 0; j < s; j++)
            {
                if (garden[i][j] == 1)
                {
                    for (k = 0; k < 4; k++)
                        if (i + dx[k] >= 0 && j + dy[k] >= 0 && i + dx[k] < s && j + dy[k] < s)
                            t[i + dx[k]][j + dy[k]] = 1; 
                    f = 1;
                }
            }
        }
        if (f == 1) answer++;
        f = 0, garden = t;
    }
    
    return answer;
}

// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다.
int main() {
    vector<vector<int>> garden1 = {{1, 0, 0}, {0, 0, 0}, {0, 0, 1}};
    int ret1 = solution(garden1);
    
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "solution 함수의 반환 값은 " << ret1 << " 입니다." << endl;
    
    vector<vector<int>> garden2 = {{1, 1}, {1, 1}};
    int ret2 = solution(garden2);
    
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "solution 함수의 반환 값은 " << ret2 << " 입니다." << endl;
}

 

위에서 설명한대로 반복문을 돌며 주어진 2차원 배열을 돌다가 꽃이 핀 곳, 즉 값이 1인 곳을 발견하면 그 주변의 상하좌우의 값을 1로 만들어준다. 이때 편하게 작업하기 위해 dx, dy에 미리 상하좌우의 좌표를 구할 수 있도록 값을 저장해 활용했다.

 

그리고 값이 바뀌었음을 표시하기 위해 변수 f를 사용했다. 값이 바뀌었으면 일 수에 체크하게 한다.

근데 아마 꽃이 안 피는 날은 없을 것 같긴 한데 혹시나 해서 넣어봤다.

위에서 말한 대로 값을 직접적으로 바꾸는 것은 문제를 일으키기 때문에 벡터 t를 따로 사용해서 값을 바꿔주고 반복문의 마지막에 적용해줬다.

 

그리고 한 바퀴를 돌 때마다(하루가 지날 때마다) 꽃이 다 피었는지 아닌지 체크하기 위해 check 함수를 따로 선언했다.

배열을 한 바퀴 돌면서 아직 0이 있으면 false, 아니면 true를 return 해준다.

true가 return 되면 반복문이 종료되고 값을 return 해준다.