[백준(Baekjoon)] 1743. 음식물 피하기 (java, BFS)

안녕하세요. 오늘은 백준 음식물 피하기 문제를 풀어보려고 합니다.

문제 링크

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

풀이

문제 해석

주어진 배열에서, 한 곳에 모여있는 최대 음식물 쓰레기의 수를 구하는 문제입니다. BFS/DFS를 사용해야겠다는 생각이 들었습니다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class bj_음식물_피하기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine(), " ");

        //세로 = N, 가로 = M, 음쓰 수 = K
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        trash = new boolean[N][M];
        visited = new boolean[N][M];
        answer = 1;

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            int trashN = Integer.parseInt(st.nextToken());
            int trashM = Integer.parseInt(st.nextToken());

            trash[trashN - 1][trashM - 1] = true;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visited[i][j] == false && trash[i][j]) {
                    bfs(i, j, N, M);
                }
            }
        }

        System.out.println(answer);
    }

    static boolean[][] trash;
    static boolean[][] visited;
    static int answer;

    static void bfs(int i, int j, int N, int M) {

        int count = 1;
        int[] dr = {0, 0, 1, -1};
        int[] dc = {1, -1, 0, 0};

        Queue<int[]> queue = new LinkedList<>();

        queue.offer(new int[]{i, j});
        visited[i][j] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();

            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dr[d];
                int nc = cur[1] + dc[d];

                if (nr > -1 && nc > -1 && nr < N && nc < M && visited[nr][nc] == false && trash[nr][nc]) {
                    visited[nr][nc] = true;
                    count++;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        if(answer < count) answer = count;
    }
}

느낀점

1) bfs 풀이법을 외워두자

bfs풀이법은 매번 거의 비슷하기 때문에 확실하게 이해하고 외워둬야겠구나 생각했습니다. 아직 bfs 풀이에 대한 이해가 부족해서 디버깅을 하면서 더 공부해야겠다고 느꼈습니다.