[백준 1743 - C++] 음식물 피하기 : DFS

www.acmicpc.net/problem/1743

1743번: 음식물 피하기

문제

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

 

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다.

 

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

 

예제 입력 1 

3 4 5

3 2

2 2

3 1

2 3

1 1

예제 출력 1 

4

 

풀이

음식물의 위치는 좌표로 입력되므로, 입력된 음식물의 뮈치를 0으로 초기화된 map에 1로 저장한다. 

그리고 전체 map에 대해서 아직 방문하지 않고, 음식물이 있는 자리에 대해 dfs 를 수행한다.

dfs함수를 main에서 처름 호출할 때 전역변수 new_size라는 변수를 0으로 초기화해주고 dfs함수에 들어올 때 마다 new_size++을 해주면 모든 재귀를 종료하고 다시 main으로 돌아왔을 때 그 음식물의 크기가 new_size에 저장되어 있다.

이를 max_size와 비교하여 max_size가 더 작은 경우엔 max_size를 업데이트 해주면 된다.

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int map[101][101];
int visited[101][101];
int R[4] = {1, -1, 0, 0};
int C[4] = {0, 0, 1, -1};

int max_size;
int new_size;

void dfs(int n, int m, int r, int c);

int main(void){
    int n, m, k;
    int r, c;

    
    scanf("%d %d %d", &n, &m, &k);
    for(int i=0; i<k; i++){
        scanf("%d %d", &r, &c);
        map[r][c] = 1;
    }
    for(int i=1; i<n+1; i++){
        for(int j=1; j<m+1; j++){
            if(map[i][j] ==1 && visited[i][j] == 0){
                new_size = 0;
                dfs(n, m, i, j);
                if(new_size > max_size){
                    max_size = new_size;
                }
            }
        }
    }
    printf("%d\n", max_size);
}

void dfs(int n, int m, int r, int c){
    int next_r, next_c;
    visited[r][c] = 1;
    new_size ++;
    
    for(int i=0; i<4; i++){
        next_r = r+R[i];
        next_c = c+C[i];
        
        if(next_r < 1 || next_r > n || next_c <1 ||next_c >m)
            continue;
        if(visited[next_r][next_c]==1)
            continue;
        if(map[next_r][next_c]==0)
            continue;

        dfs(n, m, next_r, next_c);
    }
}