[JAVA]백준 1743번: 음식물 피하기

https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

1. 문제 설명

 

문제

• 음식물들은 근처에 있는 것끼리 뭉치게 되어서 큰 음식물 쓰레기가 된다.
• 가장 큰 음식물의 크기를 구하자

조건

• 세로의 길이 N(1 <=N <=100), 가로의 길이 M(1 <=M <=100), 음식물 쓰레기의 개수(1 <=K <=N*M)

 

2. 풀이

 

DFS를 이용해서 풀 수 있는 문제이다.

 

음식물의 좌표들을 저장한 후, 반복문을 돌면서 음식물을 발견한다. 

 

발견한 음식물이, 이전에 큰 음식물로 합치는데 방문하지 않았다면 방문해서 DFS를 통해 큰 음식물로 합쳐준다.

 

 

 

*로직

1. 음식물의 위치(room)를 저장

2. 반복문을 돌면서 음식물 확인

3. 음식물이 있고, 이전에 확인하지 않았다면 DFS를 통해 탐색

4. 현재 위치에서 상, 하, 좌, 우 중에 이전에 방문하지 않고, 음식물이 있다면 dfs(next_x, next_y)+1 한 것을 ret에 더해준다.

 

3. 코드

// JAVA 11 , 메모리 : 16000KB, 시간 : 168ms

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

public class Main {

    public static int[][] move = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public static boolean[][] room;
    public static boolean[][] visit;
    public static int height, width;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int trashNum = 0, r = 0, c = 0, answer = 0;

        height = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());
        trashNum = Integer.parseInt(st.nextToken());

        // 음식물
        room = new boolean[height + 1][width + 1];
        // 방문 확인
        visit = new boolean[height + 1][width + 1];

        for (int x = 0; x < trashNum; x++) {
            st = new StringTokenizer(br.readLine());

            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            room[r][c] = true;

        }

        // 음식물이 있고, 방문하지 않았으면 탐색 시작
        for(int x=1;x<=height;x++){
            for (int y = 1; y <= width; y++) {
                if (room[x][y] && !visit[x][y]) {
                    answer = Math.max(answer, dfs(x, y)+1);
                }
            }
        }

        System.out.println(answer);

    }

    public static int dfs(int x,int y){

        visit[x][y] = true;

        int next_x = 0, next_y = 0, ret = 0;

        for (int i = 0; i < 4; i++) {
            next_x = x + move[i][0];
            next_y = y + move[i][1];

            if(next_x<=0 || next_y<=0 || next_x>height || next_y>width)
                continue;

            if(room[next_x][next_y] && !visit[next_x][next_y]){
                ret += dfs(next_x, next_y) + 1;

            }
        }

        return ret;
    }





}