[BOJ] 1743번: 음식물 피하기 (Java)

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

1743번: 음식물 피하기

 

문제

 

입력

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

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

 

출력

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

 

난이도

실버 1

 

Sol

첫 좌표부터 돌다가 음식물이 위치한 좌표에 도착하면 dfs 메서드를 돌면서 상하좌우에 위치한 음식물 노드를 찾는다. 음식물이 위치한 노드를 찾을 때마다 count를 1씩 증가시키고, 탐색할 노드가 더 이상 존재하지 않으면 음식물 크기의 최댓값과 비교해 반영한다.

public class B1743_음식물피하기 {
    public static int N, M, K;
    public static int[] dx = {0, 1, 0, -1};
    public static int[] dy = {1, 0, -1, 0};
    public static int[][] arr;
    public static boolean[][] isvisit;
    public static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(token.nextToken()); // 세로
        M = Integer.parseInt(token.nextToken()); // 가로
        K = Integer.parseInt(token.nextToken()); // 음식물 쓰레기의 개수

        arr = new int[N+1][M+1]; // padding 추가
        isvisit = new boolean[N+1][M+1];

        for(int i=0; i<K; i++) {
            token = new StringTokenizer(bf.readLine());
            int r = Integer.parseInt(token.nextToken());
            int c = Integer.parseInt(token.nextToken());
            arr[r][c] = 1; // 음식물이 떨어진 좌표
        }
        // input

        int max = 0;

        for(int i=1; i<N+1; i++){
            for(int j=1; j<M+1; j++){
                if(isvisit[i][j]==false && arr[i][j]==1){ // 방문되지 않은 노드이고, 해당 노드에 쓰레기가 떨어져 있을 경우
                    count = 1; // 쓰레기 크기
                    isvisit[i][j] = true;
                    dfs(i, j);

                    max = Math.max(max, count);
                }
            }
        }
        // operation

        System.out.println(max);
        // output
    }

    public static void dfs(int r, int c){
        for(int i=0; i<4; i++){
            int nx = r + dx[i];
            int ny = c + dy[i];

            if(nx < 1 || nx > N || ny < 1 || ny > M || isvisit[nx][ny] == true || arr[nx][ny] == 0) continue;
            // 유효한 좌표가 아닐 경우, 방문했던 노드일 경우, 해당 노드에 쓰레기가 없을 경우 탐색 종료

            isvisit[nx][ny] = true; // 방문 처리
            count++;

            dfs(nx, ny);
        }
    }
}

 

😯

이상하게 dfs랑 bfs 문제는 풀 때마다 헷갈렸는데, 이번 기회에 dfs를 확실하게 기억하고 넘어가야겠다..!