[백준] 4963 섬의 개수

 

문제를 잘 읽어보고 오자.

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

 

이 문제는 단순한 그래프 탐색 문제이다. 탐색 방법은 상관없으나, bfs로 풀이하면 가독성이 조금 더 좋은 코드가 되어서 bfs로 풀이했다. 문제 풀이는 탐색한 지점에 대해서는 체크 표시를 해 두고, 모든 좌표에 대해서 탐색을 시작해도 되는 점인지 판별하여 탐색하면 된다. 여기서 다른 문제와의 차이점은 여러 개의 테스트 케이스가 있다는 점과, 4개 방향이 아닌 8개 방향으로 그래프 탐색을 해야 한다는 것이다. 이것만 주의하면 크게 어렵지는 않다고 생각한다.

 

나의 경우에는 x좌표와 y좌표를 반대로 적은 단순한 실수 때문에 시간을 낭비했던 경험이 있다. 다음부터는 이러한 실수를 저지르지 않도록 유의해야겠다.

 

 

#include <iostream>
#include <cstring>
using namespace std;
 
/*
탐색하지 않은 좌표에 대해서 bfs를 실행하자.
x 좌표 y좌표 헷갈리지 말자. 시간 낭비했음.
*/
 
/* 움직일수 있는 방향이 8가지이므로, 미리 좌표를 만들어 놓는다. */
int move_x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int move_y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int map[50][50];
bool visited[50][50];
 
void dfs(int x, int y, int w, int h, int n)
{
    visited[y][x] = true;
    /* 8방향에 대해서 조건에 맞으면 탐색을 진행한다. */
    for (int i = 0; i < 8; i++)
    {
        int dx = x + move_x[i];
        int dy = y + move_y[i];
        if (dx >= 0 && dx < w && dy >= 0 && dy < h && map[dy][dx] && !visited[dy][dx])
            dfs(dx, dy, w, h, n);
    }
}
 
int main()
{
    //freopen("test", "r", stdin);
    int w, h, n;
    while (1)
    {
        memset(map, 0, sizeof(map));
        memset(visited, 0, sizeof(visited));
        cin >> w >> h;
        if (!w && !h)
            return (0);
        n = 1;
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                cin >> map[i][j];
 
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                if (map[i][j] && !visited[i][j])
                    dfs(j, i, w, h, n++);
        cout << n - 1 << "\n";
    }
    return (0);
}

 

알고리즘 문제 풀이는 끝이 보이지 않는다.