2146 다리만들기

아이디어

1. DFS : 맹목적 탐색방법의 하나로 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색

 - 섬의 위치 파악.

2. BFS : 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법

 - 각 섬에 대해 BFS를 실행하여(큐 섬의 개수만큼 필요.) 인접한 바다를 모두 방문.

 - 

* 비슷한 문제

2667_단지번호붙이기

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

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
const int dx[] = { 0,0,-1,1 };
const int dy[] = { -1,1,0,0 };
int n, k, chk[26][26], cnt[26 * 26];
char arr[26][26];
 
void dfs(int x, int y) {
    chk[x][y] = k;
    arr[x][y] = '0';
    cnt[k]++;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) 
            continue;
        if (arr[nx][ny] == '1') 
            dfs(nx, ny);
    }
}
 
int main() {
    int i, j;
    scanf("%d", &n);
    for (i = 0; i < n; i++) 
        scanf("%s", arr[i]);
 
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (arr[i][j] == '1' && !chk[i][j]) {
                ++k;
                dfs(i, j);
            }
        }
    }
 
    sort(cnt + 1, cnt + 1 + k);
 
    printf("%d\n", k);
    for (i = 1; i <= k; i++) 
        printf("%d\n", cnt[i]);
 
    return 0;
}