백준 4963번, 섬의 개수 — C++ 풀이

🧭 백준 4963번, 섬의 개수 — C++ 풀이

✅ 문제 설명

2차원 배열로 이루어진 지도가 주어진다.
각 칸에는 1(육지) 또는 0(바다)가 들어 있으며,
인접한 땅끼리는 상하좌우 + 대각선, 총 8방향으로 연결될 수 있다.

이 지도를 보고, 서로 연결된 육지의 덩어리(=섬)가 몇 개인지 세어야 한다.

🔹 입력

• 여러 개의 테스트케이스로 구성됨
• 각 테스트케이스의 첫 줄에는 가로(w)와 세로(h)가 주어진다 (1 ≤ w, h ≤ 50)
• 다음 h줄에는 w개의 0 또는 1로 이루어진 지도 정보가 주어진다
• 입력의 마지막 줄은 0 0 (종료 조건)

🔹 출력

• 각 테스트케이스마다 섬의 개수를 출력

🔹 예제 입력

3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
0 0

🔹 예제 출력

1
3

🧠 문제 풀이 아이디어

1. 2차원 배열을 왼쪽 위부터 오른쪽 아래까지 순회하면서,
2. 1을 발견하면, 새로운 섬으로 판단하고 탐색을 시작한다.
3. 탐색은 8방향(상, 하, 좌, 우, 대각선 네 방향) 으로 진행한다.
4. 방문할 수 있는 1이 있다면 스택에 넣고 계속 탐색을 이어간다.
5. 한 방향으로 이동했을 때 또 탐색할 1이 있다면 그것도 스택에 넣고 연쇄적으로 방문한다.
6. 스택이 비었을 때, 하나의 섬에 대한 탐색이 끝났으므로 섬 개수(count)를 증가시킨다.
7. 전체 2차원 배열을 다 순회하면 완료.

🪜 DFS with Stack - 구현 흐름 요약

• for (행)
  └ for (열)
        └ arr[y][x] == 1 && visited[y][x] == 0이면
             → DFS 시작 (stack.push({x, y}))
             → 8방향으로 인접 육지 탐색
             → 방문한 땅은 visited 처리
             → 스택이 비면 count++

📌 구현 코드 (C++)

#include <iostream>
#include <stack>

using namespace std;

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

struct Point {
    int x; // 열
    int y; // 행
};

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

    int w, h;
    while (cin >> w >> h) {
        if (w == 0 && h == 0) break;

        int arr[50][50] = {0};
        int visited[50][50] = {0};
        stack<Point> st;
        int count = 0;

        // 입력
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> arr[i][j];
            }
        }

        // 전체 지도 순회
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (arr[i][j] == 1 && visited[i][j] == 0) {
                    st.push({j, i});
                    visited[i][j] = 1;

                    while (!st.empty()) {
                        Point p = st.top(); st.pop();
                        for (int dir = 0; dir < 8; dir++) {
                            int nx = p.x + dx[dir];
                            int ny = p.y + dy[dir];

                            if (nx >= 0 && nx < w && ny >= 0 && ny < h) {
                                if (arr[ny][nx] == 1 && visited[ny][nx] == 0) {
                                    visited[ny][nx] = 1;
                                    st.push({nx, ny});
                                }
                            }
                        }
                    }

                    count++;
                }
            }
        }

        cout << count << '\n';
    }

    return 0;
}

🌀 헷갈렸던 부분 정리

🔹 stack에 좌표 2개를 넣는 방법

• C++ stack<int>에는 하나의 값만 저장 가능
• 좌표 (x, y) 같이 두 개의 값을 저장하려면:
• pair<int, int> 또는
• struct 사용

struct Point {
    int x;
    int y;
};
stack<Point> st;

🔹 좌표 해석 순서(x, y 주의)

• arr[y][x] 형태이므로, x = 열, y = 행 으로 명확히 구분해야 함
• 반대로 쓰면 인덱스 오류 또는 논리 오류 발생

🔹 dx, dy 방향 배열

• 8방향일 경우 항상 정해진 순서대로 넣는 습관 필요
• 문제마다 방향 수가 다르므로 for (int dir = 0; dir < 8; dir++) 같이 범위 명시 중요

✅ 마무리

• DFS를 재귀 없이 스택으로 구현하는 문제
• 좌표 처리와 방향 배열만 잘 정리하면 깔끔하게 해결 가능
• 입력이 많아 시간 초과가 날 수 있으니, ios::sync_with_stdio(false); cin.tie(0);는 필수!

🧩 참고

• 문제 링크: 백준 4963번 - 섬의 개수
• 관련 알고리즘 태그: DFS, BFS, 그래프 탐색, 2차원 배열, 연결 요소 탐색