[알고리즘 문제/C++]백준 1743번 : 음식물 피하기

문제 링크 : https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

DFS(깊이 우선 탐색)이나 BFS(너비 우선 탐색) 중 편한 것을 골라서 풀면 됩니다. 저의 경우 DFS를 사용해 풀었습니다.

코드

#include<iostream>
using namespace std;

int N, M, K;
int arr[102][102] = {0, };
bool visited[102][102] = {false, };
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int max1 = 0;
int value = 0;

void dfs(int x, int y){
    max1++;
    for(int i = 0; i < 4; i++){
        int X = x + dx[i];
        int Y = y + dy[i];

        if(X < 1 && Y < 1 && X > M && Y > N)
            break;
        
        if(arr[Y][X] == 1 && !visited[Y][X]){
            visited[Y][X] = true;
            dfs(X, Y);
        }
    } 
}

int main(){
    cin >> N >> M >> K;
    int X, Y;
    for(int i = 1; i <= K; i++){
        cin >> X >> Y;
        arr[Y][X] = 1;
    }

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(arr[j][i] == 1 && !visited[j][i]){
                visited[j][i] = true;
                dfs(i, j);
                if(value < max1){
                    value = max1;
                }
                max1 = 0;
            }
        }
    }

    cout << value << endl;
    return 0;
}