• Home
  • About
    • Jiwon Jeong photo

      Jiwon Jeong

      끊임없이 배우며 성장하는 엔지니어

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
    • All Categories
  • Projects

음식물 피하기(백준)

21 May 2021

Reading time ~1 minute

음식물 피하기 (1743번)

  • DFS로 풀이
#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

int n, m, k;
int cnt = 1;
int map[101][101];
bool check[101][101];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};


int dfs(int x, int y){
    check[x][y] = true;
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx <n && ny >= 0 && ny < m){
            if(!check[nx][ny] && map[nx][ny] == 1){
                check[nx][ny] = true;
                cnt++;
                dfs(nx, ny);
            }
        }
    }
    return cnt;

}

int main(){

    
    int res = 0;
    int ans;

    scanf("%d %d %d", &n, &m, &k);

    for(int i=0; i<k; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        map[a-1][b-1] = 1;   
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(!check[i][j] && map[i][j]==1){
                res = max(res, dfs(i, j));
                
                cnt = 1;
            }

        }
    }
    printf("%d\n", res);

 

}


PS Share Tweet +1