[BFS] 프로그래머스 "카카오프렌즈 컬러링북"

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

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

수행시간 : 30분 / 난이도 : 레벨 2

 

요즘 코테준비한다고 프로그래머스에서도 문제풀이를 시작했다!

우선 레벨 2 난이도를 모두 정복하고 레벨 3 으로 넘어갈 것같다.

혹시 여러분들도 프로그래머스로 코테를 준비한다면 2가지 규칙을 정해놓고 푸는 것을 추천한다.

1. 외부 IDE 절때 금지 : 실제 코테에서 대부분 IDE를 못쓰게 하므로 프로그래머스 자체 IDE를 이용해서 코딩하는 연습을 하길 추천한다. (자동완성기능 없음, 라이브러리/함수 등 내가 이미 알고 있는 지식으로만 구현하기)

2. 구글링 금지 : 문제를 푸는 동안에는 구글링을 하지 않는 것을 추천한다. 예를 들어, 올림 함수 (cmath - ceil) 를 써야되는 상황인데 모르겠다고 찾으면서 문제풀면 습관이 되서 실제 코테에서 많이 힘들어질 것 같다는 생각이다. 

 

문제는 전형적인 BFS 구현이였다.

브루트포스적으로 조건에 만족하는 모든 점들을 BFS 돌린다

1. BFS 함수내에서는 점의 개수를 세주기

2. 브루트포스내에서는 영역의 개수 세주기

 

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

int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int cnt;
bool visited[101][101];

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
void bfs(int a, int b , int m , int n, vector<vector<int>> v_map, int color){
    visited[a][b] = true;
    queue<pair<int,int>> q;
    q.push({a,b});
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0;i<4;++i){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx>=0 && nx<m && ny>=0 && ny<n){
                if(visited[nx][ny] == false && v_map[nx][ny] == color){
                    visited[nx][ny] = true;
                    cnt++;
                    q.push({nx,ny});
                }
            }
        }
    }
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    cnt=0;
    for(int i =0; i<m;++i){
        for(int j =0; j<n;++j){
            visited[i][j] = false;
        }
    }
    for(int i =0; i<m;++i){
        for(int j =0;j<n;++j){
            cnt = 1;
            if(picture[i][j] != 0 && visited[i][j] == false){
                bfs(i,j,m,n,picture, picture[i][j]);
                number_of_area++;
            }
            if(max_size_of_one_area < cnt){
                max_size_of_one_area = cnt;
            }
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}