음식물 피하기

풀이

 음식물이 있는 곳은 1로, 음식물이 아닌 곳은 0으로 그래프를 초기화한다. 음식물이 있는 인접해 있는 영역의 최대 크기를 구하는 문제다. bfs를 진행하면서 queue에 원소를 삽입할때마다 카운트를 진행하고 bfs가 끝날때 카운트 값을 return 해줘서 값을 비교하여 가장 큰 음식물을 찾으면 된다.

시간 복잡도 : O(N^2*M^2)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

import java.io.*;
import java.util.*;

public class Main {

    static int[][]graph;
    static boolean[][]visited;
    static int N,M;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static int BFS(int x, int y){
        Point point = new Point(x, y);
        int cnt = 1;
        visited[x][y] = true;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(point);
        while (!queue.isEmpty()){
            Point temPoint = queue.poll();
            int temx = temPoint.x;
            int temy = temPoint.y;
            for(int i=0; i<4; i++){
                int nx = temx+dx[i];
                int ny = temy+dy[i];
                if(0<=nx && nx<N && 0<=ny && ny<M){
                    if(graph[nx][ny]==1 && visited[nx][ny]==false){
                        visited[nx][ny]=true;
                        queue.offer(new Point(nx, ny));
                        cnt++;
                    }
                }
            }
        }
        return cnt;

    }

    public static class Point{
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        graph = new int[N][M];
        for(int i=0; i<K; i++){
            st= new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            graph[x][y] = 1;
        }
        visited = new boolean[N][M];
        int max_value = Integer.MIN_VALUE;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(graph[i][j]==1 && visited[i][j]==false){
                    max_value = Math.max(BFS(i,j), max_value);
                }
            }
        }

        bw.write(String.valueOf(max_value));
        bw.flush();
        bw.close();
        br.close();
    }
}

Python

from collections import deque
import sys
N, M, K = map(int, input().split())
graph = [[0]*M for _ in range(N)]
for i in range(K):
    a,b = map(int, sys.stdin.readline().split())
    graph[a-1][b-1] = 1

# 동 서 남 북
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs(x,y):
    queue = deque([(x,y)])
    count = 1
    graph[x][y] = 0
    while(queue):
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < N and 0<= ny < M:
                if graph[nx][ny] == 1:
                    queue.append((nx,ny))
                    graph[nx][ny] = 0
                    count += 1
    return count
max = 0
for x in range(N):
    for y in range(M):
        if graph[x][y] == 1:
            count = bfs(x,y)
            if max < count:
                max = count

print(max)