[BOJ알고리즘, C++]#4963_섬의 개수, 그래프, DFS, 미로 탐색 유형

 

#1. 문제

 

4963번: 섬의 개수

 

---

 

#2. 풀이

 

1. 그래프

 

[자료구조]#6_그래프

 

그래프 자료구조는 노드와 간선의 집합으로 이루어진 비 선형 자료구조입니다. 노드 사이의 연결 관계는 간선으로 나타내며, 방향성, 연결 강도에 따라서 다양한 형태로 표현할 수 있습니다.

 

2. DFS, 깊이 우선 탐색

 

[자료구조]#6_그래프

 

DFS(깊이 우선 탐색)은 그래프의 모든 정점을 탐색하는 방법 중 하나로, 출발점으로부터 더 이상 확장할 수 없는 단말 노드까지 우선적으로 탐색하는 방법입니다. DFS는 일반적으로 재귀 호출 혹은 스택 자료구조를 활용하여 구현할 수 있습니다.

 

3. 미로 찾기 유형! 대신, 대각선으로 인접한 칸도 이동 가능함!

 

1. 기존의 미로 찾기 유형의 문제에서 대각선으로 인접한 정점까지 이동 가능한 미로 찾기 문제입니다.
2. 우선, 주어진 그래프를 통해 각 칸을 시작점으로하는 DFS를 수행합니다.
3. 이때, 방문 여부 체크를 통해 중복 방문을 방지하고, map 상에서 이동 불가능한 지역에 대한 예외 코드를 작성해 줍니다.

 

---

 

#3. 코드

 

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

typedef pair<int,int> p;

int w, h, island;
vector<vector<int>> map;

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

void dfs(p cPos)
{
    int cy = cPos.first;
    int cx = cPos.second;

    map[cy][cx] = 0;

    for(int i=0; i<8; ++i)
    {
        int ny = cy + dy[i];
        int nx = cx + dx[i];

        if(ny < 0 || ny >= h || nx < 0 || nx >= w || map[ny][nx] == 0)
            continue;

        dfs({ny,nx});
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    while(1)
    {
        cin >> w >> h;

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

        map.clear();
        island = 0;

        map.resize(h, vector<int>(w));

        for(int i=0; i<h; ++i)
        {
            for(int j=0; j<w; ++j)
            {
                cin >> map[i][j];
            }
        }

        // dfs 수행
        for(int i=0; i<h; ++i)
        {
            for(int j=0; j<w; ++j)
            {
                if(map[i][j] == 1)
                {
                    dfs({i,j});
                    island++;
                }
            }
        }

        cout << island << '\n';
    }

    return 0;
}

 

---