음료수 얼려 먹기

N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.


제한 사항

  • 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1000)
  • 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
  • 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.


해당 문제는 얼음 틀에서 각 위치를 노드로 생각하여, 구멍이 뚫려있는 부분 (0)끼리 연결되어 있는
묶음의 개수를 DFS 알고리즘으로 구하면 쉽게 해결할 수 있다.


예를 들어 틀의 입력 값이 다음과 같을 경우

vector<vector<int>> v = {
    {0, 0, 1},
    {0, 1, 0},
    {1, 0, 1}
};

아래 그림처럼 그려지고


값이 0인 노드끼리 연결되어 있는 직사각형의 개수 3이 정답이 된다.


풀이

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool dfs(int i, int j, vector<vector<int>>& v, int N, int M){
    if (i < 0 || i >= N || j < 0 || j >= M) return false;
    if (v[i][j] == 0){
        v[i][j] = 1;
        dfs(i-1, j, v, N, M);
        dfs(i+1, j, v, N, M);
        dfs(i, j-1, v, N, M);
        dfs(i, j+1, v, N, M);
        return true;
    }
    return false;
}

int main(){
    int N, M;
    int count = 0;

    cin >> N >> M;
    vector<vector<int>> v(N, vector<int>(M));
    
    for (int i = 0; i < N; i++){
        string input;
        cin >> input;
        for (int j = 0; j < M; j++){
            v[i][j] = (input[j] - '0');
        }
    }
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            if (dfs(i, j, v, N, M)) count++;
        }
    }
    cout << count << endl;
}

해설

  1. N, M의 값을 cin으로 받아와 이차원벡터를 초기화한다.
  2. 이차원벡터의 내부 벡터 값을 순서대로 입력 받고, 할당한다.
  3. 모든 좌표를 이중 for문으로 반복하여 dfs함수를 불러온다. 이때 dfs값이 참이면 count를 +1한다.
  4. DFS는 재귀함수로 구현하였다.
  5. 최종 count를 출력한다.


input, output 예시

//input
3 3
001
010
101

//output
3



이차원벡터 초기화 vector<vector> v(N, vector(M)),
DFS 알고리즘, 재귀함수, 아스키코드 - string to int, 참조자