[BaekJoon/백준] 4963번 섬의 개수

 

이번 문제도, 바로 이전에 풀었던 문제처럼

문제집의 다른 문제들에 비해서 비교적 난이도가 낮은 편에 속해서, 뭔가 오늘 두 문제를 풀긴 풀었지만서도 찜찜하다.. ㅜㅜ

 

 

유형 자체적으로는 SCC를 찾는 문제라고 볼 수 있겠다.

2차원 배열 형태로 입력이 주어졌으므로, DFS만을 이용해서 문제를 해결할 수 있다.

 

토글 형식의 DFS(VISIT=true / dfs / VISIT=false)가 아니라, 전체 배열 완전탐색 목적의 DFS(=VISIT을 토글해주며 경우의 수를 따지지 않음) 활용을 하면 된다.

 

 

문제에서 주의할 점이 하나 있다!

문제에서 설명하듯 W와 H는 Width와 Height이므로

 

우리가 코딩하는 배열 안에서 다루게 해주려면 이 둘의 순서만 바꿔서 입력을 받아주면 된다.

// 그래프라면, SCC를 찾는 유형의 문제.
// 2차원 배열 내에서는 dfs를 이용해 간단히 구현할 수 있다.


#include <iostream>
#include <cstring>

using namespace std;

int MAP[50][50];
bool VISIT[50][50];

int W, H, K;
int COUNT;

int mx[8] = {1, -1, 0, 0, -1, -1, 1, 1};
int my[8] = {0, 0, 1, -1, -1, 1, -1, 1};


// 토글 형식이 아닌, 그냥 전체 배열을 완전탐색하는 dfs.
void dfs(int x, int y) {
    
    int tx, ty;
    
    VISIT[x][y] = true;
    
    
    for(int i = 0; i < 8; i++) {
        
        tx = x + mx[i];
        ty = y + my[i];
        
        if(tx < 0 || tx >= W || ty < 0 || ty >= H)
            continue;
        
        if(!VISIT[tx][ty] && MAP[tx][ty] == 1)
            dfs(tx, ty);
    }
    
    
}

int main() {
    
    
    while(1) {
        
        cin >> H >> W;
        
        if(W == 0 && H == 0)
            break;
        
        
        for(int i = 0; i < W; i++) {
            for(int j = 0; j < H; j++) {
                
                cin >> MAP[i][j];
                
            }
        }
        
        memset(VISIT, 0, sizeof(VISIT));
        COUNT = 0;
        
        for(int i = 0; i < W; i++) {
            for(int j = 0; j < H; j++) {
                
                if(!VISIT[i][j] && MAP[i][j] == 1) {
                    dfs(i, j);
                    COUNT++;
                }
                
            }
        }
        
        cout << COUNT << "\n";
        
        
        
        
    }
    
    
}

 

 

 

소요시간 : 15분