#4963 섬의 개수 (C++)

링크 : www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

문제 풀이는 다음과 같았다.

 

(1) 방문하지 않은 섬을 DFS한다.

(2) 해당 섬을 방문한 것으로 표기한 뒤, 해당 섬의 전방위에 섬이 있을 경우 그 위치를 DFS한다.

검은 사각형(현위치) 주변을 모두 검토한다.

(3) 만약 해당 섬의 위치가 주어진 영역을 초과하거나, 섬이 아니었거나, 이미 방문했던 전적이 있으면 DFS를 종료한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> //memset 
using namespace std;
int h = 0, w = 0, arr[52][52],ans = 0;
bool track[52][52] = { false, };
vector<int> v;

void check(int a, int b) {
    if (a > h || b > w || track[a][b]==true || arr[a][b]==0) return; // 주어진 면적을 초과했거나, 바다거나, 방문한 경험이 있으면 방문할 필요가 없다.
    track[a][b] = true;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            if (arr[a + i][b + j] == 1) check(a + i, b + j); // 해당 섬을 중심으로 xy축 기준 -1~+1을 모두 검토한다
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    while (true) {
        cin >> w >> h;
        if (h == 0 && w == 0) break;
        ans = 0;
        memset(track, false, sizeof(track)); // check문을 모두 false로 초기화한다. 
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                cin >> arr[i][j];
            }
        }
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                if (arr[i][j] == 1 && track[i][j] == false) { // 섬이고 동시에 방문해본적이 없다면 DFS를 시작한다.
                    check(i, j);
                    ans++;
                }
            }
        }
        v.push_back(ans);
    }

    for (int i = 0; i < v.size(); i++) cout << v.at(i) << "\n";

    return 0;
}

 

DFS는 양치기 전략으로 꾸준히 학습해야겠다.