[Programmers] 카카오프렌즈 컬러링북

👀 문제 설명

문제

출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)

그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다.

 

입력

입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 100
• picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
• picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

출력

리턴 타입은 원소가 두 개인 정수 배열이다. 그림에 몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴한다.

 

예제 입출력

✍🏻풀이

예전에 BFS/DFS를 하도 많이 풀어서 BFS/DFS로 푸는 문제인 건 알았는데, 내 문제는 그걸 어떻게 구현했는지 기억을 못한다는 것이다..^^ 정신차리자

아무튼 위치를 움직일 수 있도록 하는 배열 dx와 dy, 방문했는지 판단하는 벡터 isVisited, 위치를 저장하는 큐를 사용해서 BFS를 구현하는 것까진 성공했다. (색칠된 곳이 몇 개인지 구하는 것 성공)

영역이 몇 군데인지 구하는 것과, 가장 큰 영역의 크기를 구하기 위해서는 이중for문을 사용해야 했다.

각 위치에 접근하여, 만약 위치가 아직 방문하지 않은 곳이고 색이 칠해져 있다면 영역이 새로 시작하는 위치라고 판단하고, BFS함수를 호출하는 식으로 정답을 구할 수 있다. (이걸 맨날 깜빡함..)

 

코드

내가 짠 BFS코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 방문했는지 체크하는 벡터
vector<vector<bool>> isVisited;
// 상하좌우 움직이기 위한 배열
int dx[4];
int dy[4];


// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;

    // init
    isVisited.resize(m);
    for (int i = 0; i < isVisited.size(); i++) {
        isVisited.at(i).assign(n, false);
    }

    dx[0] = 0; dy[0] = -1; // 상
    dx[1] = 0; dy[1] = 1; // 하
    dx[2] = -1; dy[2] = 0; // 좌
    dx[3] = 1; dy[3] = 0; // 우

    //
    queue<pair<int, int>> Q;
    Q.push(make_pair(0, 0));
    while (!Q.empty()) {
        int curX = Q.front().first;
        int curY = Q.front().second;

        for (int i = 0; i < 4; i++) { // 움직이기
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];

            if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) // 범위를 벗어나면 다음으로
                continue;

            if (isVisited.at(nextX).at(nextY)) // 이미 방문한 곳이라면 다음으로
                continue;

            // 범위를 벗어나지 않고, 이미 방문한 곳이 아니라면?
            Q.push(make_pair(nextX, nextY)); // 큐에 (nextX, nextY)를 넣는다.
            isVisited.at(nextX).at(nextY) = true; // 방문했다고 표시 남기기

            if (picture.at(nextX).at(nextY) != 0) {
                max_size_of_one_area++;
            }
        }

        Q.pop();
    }


    vector<int> answer(2);
    answer[0] = number_of_area; // 몇 개의 영역이 있는지
    answer[1] = max_size_of_one_area; // 가장 큰 영역의 크기
    return answer;
}

 

정답

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 방문했는지 체크하는 벡터
vector<vector<bool>> isVisited;
// 상하좌우 움직이기 위한 배열
int dx[4];
int dy[4];
vector<vector<int>> vec;
int area; // 한 영역의 크기
int M, N;

void dfs(int x, int y, int color) {
    isVisited.at(x).at(y) = true;
    area++;
    
    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        
        if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) // 범위를 벗어나면 다음으로
            continue;
        
        // 아직 방문하지 않은 곳이고, 현재 위치의 색상과 같으면 재귀
        if (!isVisited.at(nextX).at(nextY) && (vec.at(nextX).at(nextY) == color)) {
            dfs(nextX, nextY, color);
        }
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    // init
    isVisited.resize(m);
    for (int i = 0; i < isVisited.size(); i++) {
        isVisited.at(i).assign(n, false);
    }
    
    dx[0] = 0; dy[0] = -1; // 상
    dx[1] = 0; dy[1] = 1; // 하
    dx[2] = -1; dy[2] = 0; // 좌
    dx[3] = 1; dy[3] = 0; // 우
    
    area = 0;
    M = m;
    N = n;
    vec = picture;
    
    //
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 현재 위치가 아직 방문하지 않은 곳이고, 색이 칠해져 있는 곳이면
            // 새로운 영역이 시작하는 위치라고 판단
            if (!isVisited.at(i).at(j) && (vec.at(i).at(j) > 0)) {
                area = 0;
                dfs(i, j, vec.at(i).at(j)); // 여기서 dfs는 재귀함수가 되므로, 만약 이 줄이 끝났다면 한 영역이 끝났다는 소리
                number_of_area++; // 영역의 개수를 +1 한다.
                max_size_of_one_area = max(area, max_size_of_one_area);
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area; // 몇 개의 영역이 있는지
    answer[1] = max_size_of_one_area; // 가장 큰 영역의 크기
    return answer;
}