백준 4963번 섬의 개수

문제 링크입니다: https://www.acmicpc.net/problem/4963

DP에서 자주 나오던 간단한 그래프 이론 문제였기 때문에 쉽게 풀 수 있는 문제였습니다.

알고리즘은 다음과 같습니다.

1. 모든 그래프 좌표를 탐색하면서 아직 방문하지 않았고 섬이면 탐색을 시작합니다.

2. 해당 좌표에서 갈 수 있는 모든 곳을 밟으며 방문했다고 표시를 합니다.

3. 섬의 개수를 추가하고 2번 과정이 끝나면 1번을 반복합니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 50;

 

int w, h;

int map[MAX][MAX]; //지도

bool visited[MAX][MAX]; //방문

 

typedef struct

{

        int dx, dy;

}dir;

 

dir direction[8] = { {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1} }; //E SE S SW W NW N NE

 

void roamIsland(int y, int x)

{

        //바다면 갈 수 없고 이미 방문한 곳을 올 필요 없다

        if (!map[y][x] || visited[y][x])

                 return;

       

        visited[y][x] = true; //해당 지점 방문 표시

 

        for (int i = 0; i < 8; i++)

        {

                 int newY = y + direction[i].dy;

                 int newX = x + direction[i].dx;

                 //범위 안에 움직일 수 있고 방문하지 않은 지점일 경우에만 돌아다닌다

                 if (newX >= 0 && newX < w && newY >= 0 && newY < h)

                         roamIsland(newY, newX);

        }

}

 

int main(void)

{

        while (1)

        {

                 cin >> w >> h;

                 if (w == 0 && h == 0)

                         break;

 

                 memset(visited, false, sizeof(visited));

 

                 for (int i = 0; i < h; i++)

                         for (int j = 0; j < w; j++)

                                 cin >> map[i][j];

 

                 int islandCnt = 0;

 

                 for(int i=0; i<h; i++)

                         for (int j = 0; j < w; j++)

                                 if (!visited[i][j] && map[i][j]) //섬이고 아직 방문하지 않은 곳이 있다면

                                 {

                                          roamIsland(i, j); //섬 안을 돌아다녀라

                                          islandCnt++;

                                 }

 

                 cout << islandCnt << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~