백준 4963번 (C++) 섬의 개수

구글링 해서 풀었다면?

그래프 이론을 공부한 뒤에도 이 문제의 해답이 떠오르지 않는다면,
이 문제의 풀이를 암기하고,
비슷한 응용 문제를 풀어보는 게 효율적인 학습법일 것 같다.

 

 

 

 

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

4963번: 섬의 개수

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <cstring>
using namespace std;
using ll = long long;
const int MAX = 52;
int map[MAX][MAX];
bool visited[MAX][MAX] ={false,};
int w, h, cnt = 0;
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

void sima(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 >= h || ny < 0 || ny >= w) {
            continue;
        }
        if (map[nx][ny] == 1 && !visited[nx][ny]) {
            sima(nx, ny);
        }
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    while (1) {
        cnt = 0;
        memset(map, 0, sizeof(map));
        memset(visited, false, sizeof(visited));
        
        cin >> w >> h;
        if (w == 0 && h == 0) break;
        
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                cin >> map[i][j];
        
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    cnt++;
                   // visited[i][j] = true;
                    sima(i, j);
                }
            }
        }
        cout << cnt << '\n';
        
    }
    return 0;
}

---

섬이 영어로 뭐더라,,, 하다가 sima... ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

응용

https://www.acmicpc.net/problem/1012
유기농 배추와 비슷한 문제이다.
비슷한 문제가 많아서 한두 개만 풀이를 보고 외워놔도 적용할 곳이 많다.

 

 

 

https://www.acmicpc.net/problem/14502
연구소는 심화문제를 풀고 싶다면 나쁘지 않은 선택일 듯하다.

14502번: 연구소