백준 4963: 섬의 개수

2667번 단지번호 붙이기와 비슷한 맥락의 문제 하지만 8방향이라는 점이 다르다. 나머지 4방향을 추가해주고 입, 출력을 조금 변경해주면 해결할 수 있다.

2667번 코드를 재활용해서 해결하려고 했는데... 조금 시간을 먹었다. 그 이유는 디버깅을 하느라 그랬는데 전역변수의 무서움을 깨달았다. 전역변수와 dfs함수에서 사용되는 변수가 겹쳐서 전역변수가 가려져 답이 이상하게 나왔다. 그리고 케이스마다 벡터와 배열을 초기화하지 않은 것이 문제였다.

플러드필이라고 불리는 이런 문제에는 인접행렬을 이용해 문제를 푼다. 인접행렬을 이용한 dfs의 시간복잡도는 O(접점의 제곱)이니 여기선 O(r*c) r은 행 c는 열이 되겠다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int g_r, g_c;
int num = 0;
vector<vector<int>> a (51);
int check[51][51];
int dr[8] = { 0, 0, 1, -1, 1 ,1, -1, -1};
int dc[8] = { 1, -1, 0, 0, -1, 1, 1, -1};
 
void dfs(int r, int c)
{
    check[r][c] = 1;
    for (int k = 0; k < 8; ++k)
    {
        int nr = dr[k] + r;
        int nc = dc[k] + c;
        if (nr >= 0 && nc >= 0 && nr < g_r && nc < g_c)
            if (check[nr][nc] == 0 && a[nr][nc] == 1)
            {
                dfs(nr, nc);
            }
    }
}
 
int main()
{    
    while (1)
    {
        num = 0;
        cin >> g_c >> g_r;
        if (g_r == 0 && g_c ==0)
            break;
        int input = 0;
        for (int i = 0; i < g_r; ++i)
        {
            for (int j = 0; j < g_c; ++j)
            {
                cin >> input;
                a[i].push_back(input);
            }
        }
        for (int i = 0; i < g_r; ++i)
            for (int j = 0; j < g_c; ++j)
            {
                if (a[i][j] == 1 && check[i][j] == 0)
                {
                    dfs(i, j);
                    num++;
                }
            }
        cout << num << endl;
        for (int i = 0; i < a.size(); ++i)
            a[i].clear();
        for (int i = 0;i < 51; ++i)
        for (int j = 0;j < 51; ++j)
            check[i][j] = 0;
    }    
    return 0;
}