[BOJ/백준] 4963 섬의 개수

● [문제번호 4963] 섬의 개수

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

4963번: 섬의 개수

 

● 알아야 할 것

: vector 자료구조와 메소드

: pair 자료구조와 메소드

: BFS

: DFS (재귀, 비재귀)

 

● 풀이 과정

: [2667 단지번호붙이기] 문제에서

각 섬(단지)의 육지(집)의 갯수를 세는 부분을 빼고

이어지는 조건(가로, 세로)에 대각선까지 추가한 것이다.

체감상 더 [4963 섬의 개수]가 더 쉬운 것 같다.

 

: BFS, DFS (비재귀)를 구현하면

육지가 있는 좌표를 이용해서 구현해야하므로

pair 자료구조를 이용한다.

 

main문

1. 모든 집을 확인하는데

2. 방문한 적 없거나, 지도에 육지가 있다면

3. 방문 체크인

4. 함수 진입

↓

BFS, DFS (비재귀) 함수

1. 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하를 확인하며 방문하면 되는 경우에

1-1. 방문 체크인

1-2. queue, stack에 저장

2. 반환은 이어져있는 육지를 섬1개로 인식해서 1반환

 

 

: DFS (재귀)

main문은 위와 동일하고

 

DFS (재귀) 함수

1. 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하를 확인하며 방문하면 되는 경우에

1-1. 방문 체크인

1-2. 재귀

2. 반환은 이어져있는 육지를 섬1개로 인식해서 1반환

 

● 주의 할 것

: 각 테스트케이스 마다 실행될 때

지도, 방문기록을 초기화해야한다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// controlX : 지도에서 움직일 때 쓰는 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
// controlY : 지도에서 움직일 때 쓰는 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
// islandMap : 섬과 바다 지도 입력
// visited : 방문기록
int controlX[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
int controlY[8] = {0, 0, -1, 1, -1, 1, -1, 1};
int islandMap[51][51];
bool visited[51][51];
int w, h;

// 넓이 우선 탐색
// 기본적인 작성 형태에서 pair 사용, 방문기록 조절
int bfs(int startRow, int startCol)
{
    // 지도의 좌표를 저장하기 위해 pair 사용
    queue<pair<int, int>> q;
    
    // BFS 함수 진입 전에 실행했기에 방문 체크인 불필요
    // visited[startRow][startCol] = true;
    q.push(pair<int, int>(startRow, startCol));
    
    while(!q.empty())
    {
        int fromRow = q.front().first;
        int fromCol = q.front().second;
        
        q.pop();
        
        // 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
        for(int i = 0; i < 8; i++)
        {
            // 방문하면 안되는 4가지
            // 1. 지도의 X축을 벗어난 경우
            if(fromRow + controlX[i] < 0 || h <= fromRow + controlX[i])
                continue;
            // 2. 지도의 Y축을 벗어난 경우
            else if(fromCol + controlY[i] < 0 || w <= fromCol + controlY[i])
                continue;
            // 3. 방문한 적이 있는 경우
            else if(visited[fromRow + controlX[i]][fromCol + controlY[i]])
                continue;
            // 4. 지도상 바다인 경우
            else if(islandMap[fromRow + controlX[i]][fromCol + controlY[i]] == 0)
                continue;
            else
            {
                visited[fromRow + controlX[i]][fromCol + controlY[i]] = true;
                q.push(pair<int, int>(fromRow + controlX[i], fromCol + controlY[i]));
            }
        }
    }
    
    // 이어져있는 섬 전체 방문 후
    // 1개라고 반환
    return 1;
}

// 깊이 우선 탐색 (비재귀)
// 기본적인 작성 형태에서 pair 사용, 방문기록 조절
int dfs(int startRow, int startCol)
{
    // 지도의 좌표를 저장하기 위해 pair 사용
    stack<pair<int, int>> s;
    
    // DFS 함수 진입 전에 실행했기에 불필요
    // visited[startRow][startCol] = true;
    s.push(pair<int, int>(startRow, startCol));
    
    while(!s.empty())
    {
        int fromRow = s.top().first;
        int fromCol = s.top().second;
        
        s.pop();
        
        // 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
        for(int i = 0; i < 8; i++)
        {
            // 방문하면 안되는 4가지
            // 1. 지도의 X축을 벗어난 경우
            if(fromRow + controlX[i] < 0 || h <= fromRow + controlX[i])
                continue;
            // 2. 지도의 Y축을 벗어난 경우
            else if(fromCol + controlY[i] < 0 || w <= fromCol + controlY[i])
                continue;
            // 3. 방문한 적이 있는 경우
            else if(visited[fromRow + controlX[i]][fromCol + controlY[i]])
                continue;
            // 4. 지도상 바다인 경우
            else if(islandMap[fromRow + controlX[i]][fromCol + controlY[i]] == 0)
                continue;
            else
            {
                visited[fromRow + controlX[i]][fromCol + controlY[i]] = true;
                s.push(pair<int, int>(fromRow + controlX[i], fromCol + controlY[i]));
            }
        }
    }
    
    // 이어져있는 섬 전체 방문 후
    // 1개라고 반환
    return 1;
}

// 깊이 우선 탐색 (재귀)
// 기본적인 작성 형태로 구현
int dfs_recursive(int startRow, int startCol)
{
    // 상, 하, 좌, 우, 좌상, 우상, 좌하, 우하
    // 이어진 모든 섬 방문
    for(int i = 0; i < 8; i++)
    {
        // 방문하면 안되는 4가지
        // 1. 지도의 X축을 벗어난 경우
        if(startRow + controlX[i] < 0 || h <= startRow + controlX[i])
            continue;
        // 2. 지도의 Y축을 벗어난 경우
        else if(startCol + controlY[i] < 0 || w <= startCol + controlY[i])
            continue;
        // 3. 방문한 적이 있는 경우
        else if(visited[startRow + controlX[i]][startCol + controlY[i]])
            continue;
        // 4. 지도상 바다인 경우
        else if(islandMap[startRow + controlX[i]][startCol + controlY[i]] == 0)
            continue;
        else
        {
            visited[startRow + controlX[i]][startCol + controlY[i]] = true;
            dfs_recursive(startRow + controlX[i], startCol + controlY[i]);
        }
    }
    
    // 이어져있는 섬 전체 방문 후
    // 1개라고 반환
    return 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    while(1)
    {
        cin >> w >> h;
        
        // 무한 반복 테스트 케이스 중지
        if(w == 0 && h == 0)
            break;
        
        // 지도 입력 + 방문기록 초기화
        for(int r = 0; r < h; r++)
        {
            for(int c = 0; c < w; c++)
            {
                cin >> islandMap[r][c];
                visited[r][c] = false;
            }
        }
        
        // 지도 내 섬 갯수
        int cnt = 0;
        
        // 모든 좌표 확인
        for(int r = 0; r < h; r++)
        {
            for(int c = 0; c < w; c++)
            {
                // {방문한 적 없고} + {섬이 있는 곳}
                if(!visited[r][c] && islandMap[r][c] == 1)
                {
                    visited[r][c] = true;
                    // {DFS재귀, DFS비재귀, BFS} 중 1개 선택
                    cnt += dfs_recursive(r, c);
                    // cnt += dfs(r, c);
                    // cnt += bfs(r, c);
                }
            }
        }
        
        cout << cnt << "\n";
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [600 - 그래프 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	13023	ABCDE	https://pirateturtle.tistory.com/269
2	1260	DFS와 BFS	https://pirateturtle.tistory.com/270
3	11724	연결 요소의 개수	https://pirateturtle.tistory.com/271
4	1707	이분 그래프	https://pirateturtle.tistory.com/272
5	2667	단지번호붙이기	https://pirateturtle.tistory.com/273
6	4963	섬의 개수	https://pirateturtle.tistory.com/274
7	2178	미로 탐색	https://pirateturtle.tistory.com/275
8	7576	토마토	https://pirateturtle.tistory.com/276
9	7562	나이트의 이동	https://pirateturtle.tistory.com/277