[BOJ] 1743 - 음식물 피하기

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/1743

1743번: 음식물 피하기

난이도: 실버 1

사용 언어: JAVA

 

식당 바닥에 음식물이 바닥에 여러 개 떨어져 있는데, 음식물들이 인접해있으면, 큰 음식물 쓰레기로 간주합니다. 인접해있다는 것은 한 음식물 상하좌우에 다른 음식물이 존재하는 경우를 말합니다.

 

입력으로부터 식당 바닥의 크기와, 떨어진 음식물의 위치 정보를 받아와서, 가장 큰 음식물 쓰레기의 크기를 구하는 것이 문제의 목표입니다.

 

풀이

이 문제는 DFS를 이용하여 쉽게 해결할 수 있습니다. DFS에 관한 기본적인 설명은 아래 문제의 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/65

[BOJ] 1303 - 전쟁 - 전투

 

 

우선 입력 값을 이용해 식당을 2차원 배열로 표현합니다. 그리고 음식물의 위치를 1, 음식물이 없는 곳을 0으로 표시합니다. 이 문제에서는 입력 값에서, 가장 왼쪽 상단의 칸이 (0,0)이 아니고 (1,1)로 표현되기 때문에 NxN의 2차원 배열이 아닌 (N+2)x(N+2) 크기의 2차원 배열을 만들어 식당에 해당하는 배열을 0으로 한번 둘러 싸주었습니다.

 

그리고 (1,1)에서부터 1로 마킹된 칸으로부터 시작되는 DFS를 통해 큰 음식물 쓰레기의 크기를 구해줍니다. DFS는 재귀 함수를 통해 구현했으며, 한 번 검사한 쓰레기가 있는 칸을 중복해서 검사하는 것을 막기 위해 해당 칸은 0으로 마킹해줍니다. 

 

하나의 큰 음식물 쓰레기에 대한 DFS가 완료될 때마다, 해당 큰 음식물 쓰레기가 지금까지의 큰 음식물 쓰레기 중 가장 큰 것인지를 검사하여 결과를 max 변수에 업데이트해줍니다. 그리고 마지막 (N,M)까지 반복문이 돌았을 때, 최후에 max에 저장된 값을 출력해줍니다.

 

import java.util.Scanner;
 
class Main {
 
    static int N,M,K;
    static int cnt = 0;
 
    public static void dfs(int x, int y, int arr[][]){
        cnt++; // 큰 음식물 쓰레기의 크기 구하기
 
        if(arr[x-1][y] == 1){ // 바로 윗 칸도 쓰레기라면?
                arr[x-1][y] = 0;
                dfs(x-1, y, arr);
        }
        if(arr[x][y+1] == 1){ // 바로 오른쪽 칸도 쓰레기라면?
                arr[x][y+1] = 0;
                dfs(x,y+1, arr);
        }
        if(arr[x+1][y] == 1){ // 바로 아랫 칸도 쓰레기라면?
                arr[x+1][y] = 0;
                dfs(x+1, y, arr);
        }
        if(arr[x][y-1] == 1){ // 바로 왼쪽 칸도 쓰레기라면?
                arr[x][y-1] = 0;
                dfs(x,y-1, arr);
        }
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i,j;
        int x,y;
        int max = 0;
 
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
 
        int arr [][] = new int [N+2][M+2];
 
        for(i=0;i<K;i++){
            x = sc.nextInt();
            y = sc.nextInt();
            arr[x][y] = 1;
        }
 
        for(i=1;i<=N;i++){
            for(j=1;j<=M;j++){
                cnt = 0;
                if(arr[i][j] == 1){
                    arr[i][j] = 0;
                   dfs(i,j,arr); // DFS 수행
                    if(cnt > max) // 지금까지의 큰 음식물 쓰레기 중 가장 큰지 확인
                        max = cnt;
                }
            }
        }
        System.out.println(max);
 
    }
}