99클럽 코테 스터디 6일차 TIL + 섬의개수(백준 4963번)

✅ 오늘의 학습 키워드

- 그래프 탐색

- DFS(깊이 우선 탐색)

- BFS(너비 우선 탐색)

---

✅ 공부한 내용

오늘은 그래프 탐색 알고리즘을 사용하여 섬의 개수를 찾는 문제를 풀어보았다.
이 문제는 2차원 격자에서 연결된 땅(1)을 하나의 섬으로 간주하며, 전체 섬의 개수를 세는 문제였다. (땅 = 1, 바다 = 0)

1. 그래프 탐색의 기본 개념

그래프 탐색 알고리즘인 DFS와 BFS는 그래프의 모든 정점을 방문하는 방법이다.
오늘 학습한 문제에서는 2차원 격자를 그래프로 보고, 각 셀을 정점으로 간주했다.

• DFS(깊이 우선 탐색): 한 방향으로 최대한 깊이 탐색한 후, 더 이상 진행할 수 없으면 다시 돌아와 다른 방향을 탐색하는 방법
• BFS(너비 우선 탐색): 현재 정점에서 가까운 정점부터 순차적으로 탐색하는 방법

 

2. 섬 개수 찾기 문제의 핵심

이 문제에서 중요한 점은 다음과 같다:

1. 땅(1)과 바다(0)로 이루어진 2차원 격자가 주어진다.
2. 인접한 땅들(상하좌우, 대각선까지 포함)은 하나의 섬을 형성한다.
3. 모든 섬의 개수를 세야 한다.

이를 해결하기 위해 DFS를 사용했다. 아직 방문하지 않은 땅을 발견할 때마다 새로운 섬의 시작점으로 보고, DFS를 통해 연결된 모든 땅을 방문 처리했다. DFS가 완료될 때마다 섬의 개수를 1 증가시켰다.

 

3. 상하좌우, 대각선 방향 이동의 구현

일반적인 상하좌우 4방향이 아닌, 대각선까지 포함한 8방향 이동이 필요했다. 이를 위해 dx, dy 배열을 다음과 같이 정의했다:

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

이 배열을 사용하면 현재 위치에서 8방향으로 이동할 수 있는 새로운 위치를 쉽게 계산할 수 있다.

 

이해가 안된다면 이렇게 보면 됩니다.  ❗ 참고 행(x축), 열(y축) ❗

    (-1, -1)      (-1, 0)        (-1, 1)
          ↖           ↑          ↗
(0, -1)  <-      현재        ->  (0, 1)
          ↙           ↓          ↘
    (1, -1)         (1,0)          (1, 1)

---

✅ 오늘의 회고

  - 😳 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 문제를 잘못 이해했다. 대각선으로도 이동할 수 있다는 조건을 놓쳐서 4방향(상하좌우)만 고려하여 DFS를 구현했다. 그 결과, 대각선으로 연결된 땅을 별도의 섬으로 카운트하게 되어 예제 출력과 다른 결과가 나왔다.

또한, 테스트 케이스가 여러 개 있고 입력의 마지막에 "0 0"이 주어진다는 점도 처음에는 놓쳤다. 그래서 단일 테스트 케이스만 처리하도록 코드를 작성했었다. 문제를 잘 읽자...!!!!!

 - 🤔 어떻게 해결했는지 (DFS 사용)

1. 대각선 이동 추가: 문제를 다시 읽고 대각선으로도 이동할 수 있다는 조건을 확인한 후, dx, dy 배열을 8방향으로 확장했다.
2. 무한 루프 구현: 입력의 끝을 처리하기 위해 while(true) 루프를 사용하고, w와 h가 모두 0일 때 루프를 종료하도록 했다.
3. 방문 배열 초기화: 각 테스트 케이스마다 방문 배열을 새로 초기화하는 것을 잊지 않았다.

  - 🤩 무엇을 새롭게 알았는지

1. 그래프 탐색의 응용: 2차원 격자 문제도 그래프 탐색 알고리즘으로 효과적으로 해결할 수 있다는 것을 다시 한번 확인했다.
2. 대각선 이동 처리: 대각선 이동을 포함한 8방향 이동을 dx, dy 배열로 간단하게 구현할 수 있다는 것을 배웠다.
3. 테스트 케이스 처리: 여러 테스트 케이스가 주어질 때 무한 루프와 종료 조건을 활용하여 처리하는 방법을 익혔다.
4. 문제 이해의 중요성: 문제 조건을 정확히 이해하는 것이 얼마나 중요한지 다시 한번 느꼈다. 작은 조건 하나(대각선 이동)를 놓치면 전혀 다른 결과가 나올 수 있다.

이번 학습을 통해 그래프 탐색 알고리즘의 활용 범위가 매우 넓다는 것을 다시 한번 깨달았다.
앞으로도 다양한 문제에 DFS와 BFS를 적용해 보며 응용력을 키워야겠다. 더 공부하자...

---

✅ 전체 코드 (DFS 사용)

#include <iostream>
#include <vector>
using namespace std;

// 상하좌우 및 대각선 이동을 위한 방향 배열
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

// DFS 함수 정의
void dfs(vector<vector<int>>& map, vector<vector<bool>>& visited, int x, int y, int w, int h) {
    
    // 현재 위치를 방문 표시
    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 && map[nx][ny] == 1 && !visited[nx][ny]) {
            // 새 위치에서 DFS 계속 진행
            dfs(map, visited, nx, ny, w, h);
        }
    }
}

int main() {
    while (true) {
        int w, h;
        cin >> w >> h;
        
        if (w == 0 && h == 0) {
            break;
        }
        
        // 지도 정보 저장
        vector<vector<int>> map(h, vector<int>(w));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> map[i][j];
            }
        }
        
        // 방문 여부 저장 배열 초기화
        vector<vector<bool>> visited(h, vector<bool>(w, false));
        
        // 섬의 개수 카운트
        int landCnt = 0;
        
        // 전체 지도를 순회하면서 새로운 섬 찾기
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                // 땅이고 아직 방문하지 않았다면, 새로운 섬 시작
                if (map[i][j] == 1 && !visited[i][j]) {
                    dfs(map, visited, i, j, w, h); // DFS로 섬의 모든 땅 방문
                    landCnt++; // 섬 개수 증가
                }
            }
        }
        
        cout << landCnt << endl;
    }
    
    return 0;
}