백준 / 4963번 / 섬의 개수 / C++

# 출처 : https://www.acmicpc.net/problem/4963

처음엔 BFS를 써서 풀고자 큐를 사용했으나 뭔가 원하는 방향으로 진행이 되지 않길래

스택을 써서 풀었다. 그렇게 풀고 다른 사람들의 답을 보니 재귀를 사용해서 훨씬 간단하게 풀었어서

재귀 연습겸 재귀로도 풀어보았다.

# 스택 사용

#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
 
int C, R, cnt;
int map[51][51], dist[51][51];
const int dR[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
const int dC[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
stack<pair<int, int>> S;
bool isInRange(int row, int col)
{
    return (row >= 0 && row < R) && (col >= 0 && col < C);
}
void DFS()
{
    while (!S.empty())
    {
        int curR = S.top().first;
        int curC = S.top().second;
        S.pop();
 
        if (dist[curR][curC] == -1)
            dist[curR][curC] = 0;
 
        for (int i = 0; i < 8; ++i)
        {
            int nextR = curR + dR[i];
            int nextC = curC + dC[i];
            if (isInRange(nextR, nextC) && map[nextR][nextC] == 1)
            {
                if (dist[nextR][nextC] == -1)
                {
                    dist[nextR][nextC] = dist[curR][curC] + 1;
                    S.push({ nextR, nextC });
                }
                else
                {
                    if (dist[nextR][nextC] > dist[curR][curC] + 1)
                    {
                        dist[nextR][nextC] = dist[curR][curC] + 1;
                    }
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    while (true)
    {
        cin >> C >> R;
        if (C == 0 && R == 0)
            break;
        memset(map, 0, sizeof(map));
        memset(dist, -1, sizeof(dist));
        cnt = 0;
        for (int i = 0; i < R; ++i)
        {
            for (int j = 0; j < C; ++j)
            {
                cin >> map[i][j];
                if (map[i][j] == 1)
                    S.push({ i, j });
            }
        }
        DFS();
        for (int i = 0; i < R; ++i)
        {
            for (int j = 0; j < C; ++j)
            {
                if (dist[i][j] == 0)
                    ++cnt;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

# 재귀 사용

#include <iostream>
using namespace std;
bool arr[52][52];
int dR[8] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dC[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };
int R, C, cnt;
 
bool available(int row, int col) {
    return row >= 0 && row < R && col >= 0 && col < C;
}
 
void recur(int row, int col) {
    arr[row][col] = 0;
    for (int i = 0; i < 8; ++i)
        if (arr[row + dR[i]][col + dC[i]] == true && available(row + dR[i], col + dC[i]))
            recur(row + dR[i], col + dC[i]);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    while (true) {
        cin >> C >> R;
        if (R == 0 && C == 0)   break;
        cnt = 0;
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j)
                cin >> arr[i][j];
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j) {
                if (arr[i][j] == true) {
                    recur(i, j);
                    ++cnt;
                }
            }
        cout << cnt << '\n';
    }
}