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

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

프로그래머스

int Row;
int Column;
bool Visited[101][101];
vector<pair<int, int>> Direction;
 
struct Node
{
    int row;
    int column;
 
    Node(int _row, int _column) : row(_row), column(_column) {};
};
 
int BFS(int startRow, int startColumn, vector<vector<int>>& picture) // 영역크기 리턴.
{
    queue<Node> q;
    int count = 0;
    Visited[startRow][startColumn] = true;
    int standColor = picture[startRow][startColumn];
    q.push(Node(startRow, startColumn));
 
    while (!q.empty())
    {
        Node popedNode = q.front();
        q.pop();
        count++;
 
        int curRow = popedNode.row;
        int curColumn = popedNode.column;
 
        for (int i = 0; i < Direction.size(); i++)
        {
            int nextRow = curRow + Direction[i].first;
            int nextColumn = curColumn + Direction[i].second;
 
            if (nextRow < 0 || nextRow > Row - 1) continue;
            if (nextColumn < 0 || nextColumn > Column - 1) continue;
 
            if (!Visited[nextRow][nextColumn] && picture[nextRow][nextColumn] == standColor)
            {
                Visited[nextRow][nextColumn] = true;
                q.push(Node(nextRow, nextColumn));
            }
        }
    }
 
    return count;
}
 
 
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    vector<int> answer;
 
    Row = m;
    Column = n;
    fill(&Visited[0][0],&Visited[m][n], false);
    Direction = { make_pair(-1,0),make_pair(1,0),make_pair(0,-1),make_pair(0,1) };
 
    int areaCount = 0;
    int areaMaxSize = 0;
 
    for (int i = 0; i < Row; i++)
    {
        for (int j = 0; j < Column; j++)
        {
            if (!Visited[i][j] && picture[i][j] != 0)
            {
                areaCount++;
                int areaSize = BFS(i,j,picture);
                if (areaSize > areaMaxSize) areaMaxSize = areaSize;
            }
        }
    }
 
    answer.push_back(areaCount);
    answer.push_back(areaMaxSize);
 
    return answer;
}

 

BFS푸는 감?을 잃지 않기위해 풀어본 문제다. 각 연결된 영역들의 개수와 영역의 최대크기를 구하는 문제다.

방문하지 않은 노드에 대해서만 0,0부터 시작해서 m,n까지 BFS를 진행한다.

어차피 방문하지않은것만 하기 때문에 시간복잡도에 걸릴일은 없다.

BFS에서는 인풋으로 들어온 좌표부터 시작해서 상하좌우를 탐색하며 standColor값이 같은것만 큐에 넣는다.

picture에서 0은 색깔이 칠해지지 않은것을 의미하기떄문에 0은 무시한다.