알고리즘 :: 백준 :: DFS :: 4963 :: 섬의 개수

Embedded June·2020년 7월 26일
0

알고리즘::백준

목록 보기
25/109

문제

문제접근

  • 전형적인 DFS의 그래프 세그먼트 개수 구하기 문제다.
  • 모든 정점에 대해 DFS를 수행한 뒤 DFS가 종료됨은 각 세그먼트에 대해 탐색이 끝났음을 의미하므로 카운팅해주면 전체 섬의 개수를 구할 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;

int w, h;
vector<vector<bool>> map;
vector<vector<bool>> visited;
constexpr int dir[8][2] {
    {1, 0}, {1, 1}, {0, 1}, {-1, 1},        // ↑ ↗ → ↘
    {-1, 0}, {-1, -1}, {0, -1}, {1, -1}     // ↓ ↙ ← ↖
};

bool isRightRange(int y, int x) {
    return (0 <= y && y < h && 0 <= x && x < w);
}
void dfs(int y, int x) {
    if (visited[y][x]) return;

    visited[y][x] = true;
    for (int i = 0; i < 8; ++i) {
        int nextY = y + dir[i][0], nextX = x + dir[i][1];
        if (isRightRange(nextY, nextX) && map[nextY][nextX]) dfs(nextY, nextX);
    }
}

int solve() {
    int fragment = 0;
    for (int y = 0; y < h; ++y)
        for (int x = 0; x < w; ++x)
            if (map[y][x] && !visited[y][x]) {
                dfs(y, x);
                fragment++;
            }
    return fragment;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    while(true) {
        cin >> w >> h;
        if (w == 0 && h == 0) break;

        map = visited = vector<vector<bool>> (h, vector<bool>(w, false));
        
        for (int y = 0; y < h; ++y)
            for (int x = 0; x < w; ++x) {
                int var = 0;    cin >> var;
                map[y][x] = (var == 1);
            }
        cout << solve() << '\n';
    }
}
  • vector<bool> 사용을 지양하고 bitset또는 일반 bool타입 배열을 써야한다는 걸 알면서도 사용했다. 참 까다로운 선택사항인것 같다.
  • 8방향은 시계방향으로 구현하였다.

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글