문제 푼 날짜 : 2021-08-10

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1829

접근 및 풀이

DFS와 BFS를 이용하면 쉽게 풀 수 있는 문제였다.
아래와 같은 알고리즘을 따라 구현하였다.

1. 주어진 배열을 탐색하면서 방문하지 않았고 0이 아닌 요소(색)을 찾는다.
2. 찾는 순간 영역의 개수를 +1 해주고 그 색과 같은 영역의 크기를 찾는다.
   2-1. 지금까지 찾은 영역의 크기 중 가장 큰 크기로 업데이트 해준다.
3. 1.부터 다시 진행하며 배열을 전부 탐색하면 종료한다.

코드 (DFS)

#include <vector>
#include <cstring>

using namespace std;

struct Point {
    int y, x;
};

vector<vector<int>> Picture;
int M, N, cnt;
bool visited[100][100];

int dir[4][2] = {{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }};

void dfs(Point src, int color) {
    visited[src.y][src.x] = true;
    
    for (int i = 0; i < 4; i++) {
        int nextY = src.y + dir[i][0];
        int nextX = src.x + dir[i][1];
        
        if (nextY < 0 || nextY >= M || nextX < 0 || nextX >= N) {
            continue;
        }
        if (visited[nextY][nextX] == true) {
            continue;
        }
        if (Picture[nextY][nextX] != color) {
            continue;
        }
        cnt++;
        dfs({ nextY, nextX }, color);
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    M = m, N = n, Picture = picture;
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    memset(visited, false, sizeof(visited));
    
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i][j] == false && Picture[i][j] != 0) {
                number_of_area++;
                cnt = 1;
                dfs({ i, j }, Picture[i][j]);
                max_size_of_one_area = max(max_size_of_one_area, cnt);
            }
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

코드 (BFS)

#include <vector>
#include <queue>
#include <cstring>

using namespace std;

struct Point {
    int y, x;
};

int dir[4][2] = {{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }};

vector<vector<int>> Picture;
int M, N;
bool visited[100][100];

int bfs(Point src, int color) {
    int cnt = 1;
    queue<Point> q;
    q.push(src);
    visited[src.y][src.x] = true;
        
    while (!q.empty()) {
        Point now = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nextY = now.y + dir[i][0];
            int nextX = now.x + dir[i][1];
            if (nextY < 0 || nextY >= M || nextX < 0 || nextX >= N) {
                continue;
            }
            if (visited[nextY][nextX] == true){
                continue;
            }
            if (Picture[nextY][nextX] != color) {
                continue;
            }
            q.push({ nextY, nextX });
            visited[nextY][nextX] = true;
            cnt++;
        }
    }
    return cnt;
}

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

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (Picture[i][j] != 0 && visited[i][j] == false) {
                number_of_area++;
                max_size_of_one_area = max(max_size_of_one_area, bfs({ i, j }, Picture[i][j]));
            }
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

결과

피드백

DFS, BFS를 손쉽게 구현할 수 있도록 반복 숙달하도록 하자.