[HackerRank] Connected Cells in a Grid

HackerRank 알고리즘 문제 풀이

분류

Practice > Algorithms > Search

문제 링크 : https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem

풀이

0과 1로 이루어진 2차원 벡터 matrix가 주어진다. 1은 채워진 셀이고 0은 비워진 셀인데, 채워진 셀은 인접한 8방향(상하좌우 방향+대각선4방향)에 채워진 셀이 존재하는 경우 서로 연결될 수 있다. 이러한 조건으로 연결된 셀 중에서 가장 큰 영역을 구하면 된다.

간단한 탐색 문제이므로 DFS 또는 BFS를 활용하여 풀 수 있다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

// Complete the connectedCell function below.

const int dr[] = {-1,-1,-1,0,0,1,1,1};
const int dc[] = {-1,0,-1,-1,1,-1,0,1};
bool visited[10][10];
int R, C, cnt;

void dfs(const vector<vector<int>>& matrix, int r, int c) {
    ++cnt;
    visited[r][c] = true;
    for (int d = 0; d != 8; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nc < 0 || nr == R || nc == C
            || visited[nr][nc] || matrix[nr][nc] == 0) continue;
        dfs(matrix, nr, nc);
    }
}

int connectedCell(vector<vector<int>> matrix, int n, int m) {
    R = n;
    C = m;
    int ans = 0;
    for (int i = 0; i != R; ++i) {
        for (int j = 0; j != C; ++j) {
            if (visited[i][j] || matrix[i][j] == 0) continue;
            cnt = 0;
            dfs(matrix, i, j);
            if (ans < cnt) ans = cnt;
        }
    }
    return ans;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    int m;
    cin >> m;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    vector<vector<int>> matrix(n);
    for (int i = 0; i < n; i++) {
        matrix[i].resize(m);

        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    int result = connectedCell(matrix, n, m);

    fout << result << "\n";

    fout.close();

    return 0;
}