Programmers Level 2: 카카오프렌즈 컬러링 북

https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북

풀이법

1) BFS를 활용하여 문제를 해결했다. DFS를 쓰는 것이 더 좋을 수도 있으나, 손에 익는 방식으로 문제를 빠르게 푸는 연습을 통해 programmers 툴을 익혀보았다.

2) visited 배열을 선언하여 방문한 곳을 표시하고, 같은 색으로 이뤄진 공간을 확인하기 위해 상하좌우의 배열을 활용하였다.

int vx[4]={1,0,0,-1};
int vy[4]={0,1,-1,0};

 

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

bool visited[101][101];
int vx[4]={1,0,0,-1};
int vy[4]={0,1,-1,0};
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int number_of_area;
int max_size_of_one_area;
void bfs(int m, int n, vector<vector<int>> picture,int i,int j)
{
    queue<pair<int,pair<int,int>>> q;
    visited[i][j]=true;
    q.push({i,{j,1}});
    number_of_area++;
    int count=0;
    while(!q.empty())
    {
        int nowX=q.front().first;
        int nowY=q.front().second.first;
        int cnt=q.front().second.second;
        q.pop();
        count++;
        for(int k=0;k<4;k++)
        {
            int nextX=nowX+vx[k];
            int nextY=nowY+vy[k];
            if(nextX<0||nextY<0||nextX>=m||nextY>=n)
                continue;
            if(!visited[nextX][nextY]&&(picture[nowX][nowY]==picture[nextX][nextY]))
            {
                visited[nextX][nextY]=true;
                q.push({nextX,{nextY,cnt+1}});
            }
        }
    }
    max_size_of_one_area=max(count,max_size_of_one_area);
}
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    number_of_area = 0;
    max_size_of_one_area = 0;
    for(int i=0; i<101;i++)
    {
        for(int j=0; j<101;j++)
        {
            visited[i][j]=false;
        }
    }
    for(int i=0; i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(!visited[i][j]&&picture[i][j]>0)
                bfs(m,n,picture,i,j);
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}