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

문제출처

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

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

 

문제풀이

삼성 역량테스트를 준비할때 많이 풀어본 유형이다. 기본적인 BFS문제로 완전탐색을 했다. BFS탐색을 할때마다 영역의 개수가 1개씩 증가하고 각 영역의 크기를 구하면 되는 문제다.

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%B9%B4%EC%B9%B4%EC%98%A4%ED%94%84%EB%A0%8C%EC%A6%88%20%EC%BB%AC%EB%9F%AC%EB%A7%81%EB%B6%81.cpp

sw93/algorithm

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int dy[] = { 0, -1, 0, 1 };
const int dx[] = { 1, 0, -1, 0 };
bool visit[100][100] = { 0, };
int bfs(int sy, int sx, int m, int n, vector<vector<int>> picture) {
    int color = picture[sy][sx];
    int size = 1;
    queue<pair<int, int> > q;
    q.push(make_pair(sy, sx));
    visit[sy][sx] = 1;
    
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for (int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny<0 || nx<0 || ny>=m || nx>=n || visit[ny][nx] || picture[ny][nx] != color) continue;
            visit[ny][nx] = 1;
            q.push(make_pair(ny, nx));
            size++;
        }
    }
    return size;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            visit[y][x] = 0;
        }
    }
    int areaCount = 0;
    int maxAreaCount = 0;
    for (int y=0; y<m; y++) {
        for (int x=0; x<n; x++) {
            if (visit[y][x] || picture[y][x] == 0) continue;
            maxAreaCount = max(maxAreaCount, bfs(y, x, m, n, picture));
            areaCount++;
        }
    }
    vector<int> answer(2);
    answer[0] = areaCount;
    answer[1] = maxAreaCount;   
    return answer;
}