음식물 피하기

문제

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

예제 입력 1 복사

예제 출력 1 복사

힌트

# . . .
. # # .
# # . .

위와 같이 음식물이 떨어져있고 제일큰 음식물의 크기는 4가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M,K;
    static int[][] A;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 통로 세로 길이
        M = Integer.parseInt(st.nextToken()); // 통로 가로 길이
        K = Integer.parseInt(st.nextToken()); // 음식물 쓰레기 개수

        A = new int[N][M]; // 통로 초기화
        visited = new boolean[N][M]; // 방문배열 초기화

        // 음식물 쓰레기 좌표 입력받기
        for (int i=0; i<K; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            A[r-1][c-1] = 1;
        }

        int max = 0;
        for (int i=0; i<N; i++){
            for (int j=0; j<M; j++){
                if (A[i][j] == 1 && !visited[i][j]){
                    max = Math.max(max, BFS(i, j));
                }
            }
        }

        System.out.println(max);
    }
    private static int BFS(int r, int c){
        int count = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{r, c}); // 큐에 현재좌표 넣기
        visited[r][c] = true; // 방문처리

        // BFS 탐색시작
        while (!q.isEmpty()){
            int[] now = q.poll(); // 현재좌표
            visited[now[0]][now[1]] = true; // 방문체크
            count++;

            for (int i=0; i<4; i++){ // 상하좌우 좌표탐색
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (isIn(nx,ny) && !visited[nx][ny]){
                    visited[nx][ny] = true; // 방문체크
                    if (A[nx][ny] == 1){
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
        return count;
    }
    private static boolean isIn(int x, int y){
        return x>=0 && y>=0 && x<N && y<M;
    }
}

BFS를 활용한 문제
1번의 BFS 탐색에서 count되는 값 중 최댓값을 찾으면 된다.
음식물 쓰레기 좌표값을 입력받아 배열 A에 1로 표시해준다.
모든 표시가 끝나면 모든 좌표를 순회하면서, 음식물 쓰레기를 발견하고 아직 방문하지 않은 좌표라면 BFS탐색을 시작한다.

BFS

    private static int BFS(int r, int c){
        int count = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{r, c}); // 큐에 현재좌표 넣기
        visited[r][c] = true; // 방문처리

        // BFS 탐색시작
        while (!q.isEmpty()){
            int[] now = q.poll(); // 현재좌표
            visited[now[0]][now[1]] = true; // 방문체크
            count++;

            for (int i=0; i<4; i++){ // 상하좌우 좌표탐색
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (isIn(nx,ny) && !visited[nx][ny]){
                    visited[nx][ny] = true; // 방문체크
                    if (A[nx][ny] == 1){
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
        return count;
    }

큐에 파라미터로 받은 좌표값을 넣고 방문처리한다.
큐가 빌때까지 아래 동작을 반복수행한다.
- 현재 좌표를 poll한다. (now)
- 현재좌표(now)의 상하좌우 좌표를 탐색한다.
- 좌표탐색이 유효한 좌표이고, 아직 방문하지 않았다면 방문체크 해준다.
- 만약 탐색좌표가 음식물쓰레기가 있는 좌표라면 큐에 넣어준다.