음료수 얼려 먹기

'이것이 코딩테스드다 with 파이썬' 실전문제 5-3번 음료수 얼려 먹기 문제입니다.

 

DFS를 사용하여 해결하는 문제입니다.

 

 

□ 소스 코드

#include <bits/stdc++.h>

int n,m;
int** input;

bool dfs(int x,int y){
    
    // 범위를 벗어나는 경우 false 리턴
    if(x<0 || y<0 || x>=n || y>=m )
        return false;
    
    //상하좌우를 탐색하고 찾은 경우 true 리턴
    if(input[x][y] == 0){
        input[x][y] = 1;
        dfs(x-1, y);
        dfs(x+1, y);
        dfs(x, y-1);
        dfs(x, y+1);
        return true;
    }
    
    return false;
}


void frozenJuice(){
    
    cin>>n>>m;
    input = new int* [n];
    
    for(int i=0;i<n;i++)
        input[i] = new int[m];
    
    
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%1d",&input[i][j]);
        
    int count = 0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(dfs(i,j) == true)
                count++;
        
    
    cout<<count<<endl;
    
    for(int i=0;i<n;i++)
        delete []input[i];
    delete [] input;
}

 

해결방법

1. 모든 배열을 하나씩 탐색한다.
2. 0이 되는 부분이 있는 경우 해당 지점에서 상하좌우를 탐색한다.
3. 탐색할 때 1이거나 값이 범위를 초과하는 경우 false를 리턴한다.
4. 탐색할 때 0인 경우 2번 과정을 반복한다.

재귀함수에 잘 알고 있으면 손쉽게 풀 수 있는 것 같다.