[백준(BOJ)] 4963번: 섬의 개수 (DFS/BFS, C++)

📝 문제풀이 과정

---

BOJ:2667 (단지번호붙이기) 문제를 풀어보면, 조금만 응용해서 쉽게 풀 수 있다.

이 문제에서는, 섬이 있으면 1로 표시하는데, graph[x][y] 기준으로 다음의 8가지 경우를 걸어서 갈 수 있는 경로로 간주한다.

x-1 y-1
x-1 y
x-1 y+1
x y-1
x y+1
x+1 y-1
x+1 y
x+1 y+1

 

따라서 아래와 같이 위의 8가지 경우의 graph[x][y]에서 x좌표와 y좌표가 가질 수 있는 수를 나타낼 수 있다.

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

8가지의 경우가 있으므로 DFS 함수에서 nx = x + dx[i], ny = y + dy[i]로 다음 방문할 정점을 정하고, 만약 1의 값을 가지고 아직 방문하지 않았으면 DFS 함수를 호출해서 방문한다. 재귀함수를 통해 구현한 DFS 탐색이다.

 

처음 방문했던 정점을 기준으로 시작해서 1의 값을 가지는 모든 연결된 경로 방문이 끝나면 main 함수에서 가장 먼저 DFS 함수를 호출한 main 함수로 리턴한다. 리턴 후 count를 증가시켜서 하나의 섬에 방문했음을 나타낸다.

 

 

 

 

💻 C++ 제출코드

---

처음에는 STL에 있는 함수인 deque를 사용해서 graph를 나타냈고, 이후 일반 2차원 배열로도 구현해봤다.

#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int visited[50][50];

void DFS(int x, int y, deque<int> *graph, int w, int h){
    visited[x][y] = 1;
    for(int i=0; i<8; i++){
        int nx = x + dx[i]; int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
        if(graph[nx][ny] == 1 && !visited[nx][ny]) DFS(nx, ny, graph, w, h);
    }
}

int main(){
    while(true){
        int w, h;
        scanf("%d %d", &w, &h);
        if(w == 0 && h == 0) break;
        deque<int> graph[h];
        int cnt=0;
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                int num; scanf("%d", &num);
                graph[i].push_back(num);
                visited[i][j] = 0;
            }
        }
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(graph[i][j] == 1 && !visited[i][j]) { 
                    DFS(i, j, graph, w, h); 
                    cnt++; 
                }
            }
        }
        printf("%d\n", cnt);
    }
}

#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int visited[50][50];
int graph[50][50];

void DFS(int x, int y, int w, int h){
    visited[x][y] = 1;
    for(int i=0; i<8; i++){
        int nx = x + dx[i]; int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
        if(graph[nx][ny] == 1 && !visited[nx][ny]) DFS(nx, ny, w, h);
    }
}

int main(){
    while(true){
        int w, h;
        scanf("%d %d", &w, &h);
        if(w == 0 && h == 0) break;
        int cnt=0;
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                int num; scanf("%d", &graph[i][j]);
                visited[i][j] = 0;
            }
        }
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(graph[i][j] == 1 && !visited[i][j]) { 
                    DFS(i, j, w, h); 
                    cnt++; 
                }
            }
        }
        printf("%d\n", cnt);
    }
}

 

 

 

👏 결과

---