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

문제

✔ 난이도 - Silver 1

설명

bfs

(0,0)부터 쭉 훑으면서 1 있으면 거기부터 탐색시작. 오른쪽 -> 아래 -> 왼쪽 -> 위 순으로 탐색
1이 있으면 음식물 크기 ++, 방문표시하기

가장 큰 음식물인지 아닌지는 따로 max값으로 판별

풀이

public class Main {

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int Row = Integer.parseInt(st.nextToken());
        int Col = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] graph = new int[Row][Col];

        while (K-- > 0){
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken()) - 1;
            int col = Integer.parseInt(st.nextToken()) - 1;

            graph[row][col] = 1;
        }
        // 음식물 위치 저장 완료

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

        int maxCount = 0;
        int count = 0;

        for(int i = 0; i < Row; i++){
            for (int j = 0; j < Col; j++) {
                if (graph[i][j] == 0) continue;

                count = bfs(graph, i, j, dr, dc, Row, Col);
                if (count > maxCount) {
                    maxCount = count;
                }
            }
        }
        sb.append(maxCount);
        
        System.out.println(sb);
    }

    private static int bfs(int[][] graph, int row, int col, int[] dr, int[] dc, int Row, int Col){
        Queue<int[]> queue = new LinkedList<>();
        int count = 0;
        queue.offer(new int[] {row, col});
        count++;
        graph[row][col] = 0;

        while(!queue.isEmpty()){
            int[] node = queue.poll();
            int cr = node[0];
            int cc = node[1];

            for (int i = 0; i < 4; i++){
                int nr = cr + dr[i];
                int nc = cc + dc[i];

                if (nr < 0 || nc < 0 || nr >= Row || nc >= Col || graph[nr][nc] == 0) continue;

                queue.offer(new int[] {nr, nc});
                count++;
                graph[nr][nc] = 0;
            }
        }   

        return count;
     }
}

⏰ 시간복잡도

$O(N^2)$