관리 메뉴

차근차근

[백준 4963] 섬의 개수 본문

대학교/Algorithm

[백준 4963] 섬의 개수

SWKo 2020. 2. 16. 14:27

0. 제목

  • 백준 4963 섬의 개수
  • BOJ 4963 섬의 개수
  • C++ 4963 섬의 개수

1. 문제

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


2. 풀이

  • 백준 2667 단지번호붙이기 문제와 비슷한 문제이다. 2667번은 상하좌우를 따지는 것이었다면 이 문제에서는 대각선까지 고려해야한다.
  • dfs에서는 여덟 방향 모두 탐색을 하면서 좌표가 0보다 작아지거나 주어진 넓이나 높이보다 같거나 커지면 넘어가면서 탐색한다.
  • 재귀적으로 코드를 작성했으므로 여덟방향 중 이어진 부분이 있으면 그 덩어리를 전부 탐색완료 할 것이다.
  • main함수에서 탐색을 할 때 값이 1이면서 방문하지 않은 부분을 반복문 내에서 탐색한다. 한 덩어리를 탐색완료 할 때마다 덩어리개수를 1씩 증가시켜준다.
  • 탐색을 모두 마치면 정답이 나온다.
  • 주의할 점으로는 입력을 받을 때 height, width 순서로 입력을 받아야한다. 왜냐하면 arr[0][0], arr[0][1] 과 같이 좌표를 지정할 때 arr[height][width] 로 지정하기 때문이다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 50
 
int arr[MAX][MAX];
bool visited[MAX][MAX];
 
int w, h;
int cnt = 0;
 
int dx[8= {-1,0,1,-1,1,-1,0,1};
int dy[8= {1,1,1,0,0,-1,-1,-1};
 
void dfs(int x, int y){
    visited[x][y] = true;
    for(int i = 0; i < 8; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= w || ny < 0 || ny >= h)
            continue;
        if(arr[nx][ny] == 1 && visited[nx][ny] == false)
            dfs(nx, ny);
    }
}
 
int main(int argc, const char * argv[]) {
    while(true){
        memset(arr, 0sizeof(arr));
        memset(visited, falsesizeof(visited));
        cnt = 0;
        cin >> h >> w;//입력 받는 순서 주의할 것
        if(h == 0 && w == 0)
            break;
        for(int i = 0; i < w; i++){
            for(int j = 0; j < h; j++){
                cin >> arr[i][j];
            }
        }
        for(int i = 0; i < w; i++){
            for(int j = 0; j < h; j++){
                if(arr[i][j] == 1 && visited[i][j] == false){
                    cnt++;
                    dfs(i, j);
                }
            }
        }
        cout << cnt << '\n';
    }
 
    return 0;
}
 

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 15953] 상금 헌터  (0) 2020.02.17
[백준 2133] 타일 채우기  (0) 2020.02.17
[백준 1966] 프린터 큐  (0) 2020.02.16
[백준 2170] 선 긋기  (0) 2020.02.15
[백준 1699] 제곱수의 합  (0) 2020.02.15
0 Comments
댓글쓰기 폼