[BOJ] 백준 1743 - 음식물 피하기 풀이

1. 문제

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

1743번: 음식물 피하기

 

2. 풀이

백준에서 탐색 문제로 분류되어 있다. BFS, DFS의 개념을 알고 있다면 크게 어려울 것이 없는 문제였다.
핵심은 음식물 쓰레기가 있는 지점부터 시작하여 탐색을 진행하는데, 상하좌우에 쓰레기가 있으면 하나의 쓰레기 묶음으로 처리되므로, 다음 번을 탐색할 때 음식물 쓰레기가 있는지를 판단해주어 탐색을 하면 충분히 해결된다.

 

3. 소스 코드

- DFS

package dfs;

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

public class Main {
    static int N, M, K;
    static int result = Integer.MIN_VALUE;
    static int tempResult = 0;

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int xPoint = Integer.parseInt(st.nextToken()) - 1;
            int yPoint = Integer.parseInt(st.nextToken()) - 1;

            map[xPoint][yPoint] = -1;
        }

        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j] && map[i][j] == -1) {

                    tempResult += 1;
                    dfs_trash(i, j);

                    result = Math.max(tempResult, result);
                    tempResult = 0;
                }
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs_trash(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int xf = x + dx[i];
            int yf = y + dy[i];

            if (xf >= 0 && yf >= 0 && xf < N && yf < M && !visited[xf][yf]) {
                if (map[xf][yf] == -1) {
                    tempResult += 1;
                    dfs_trash(xf, yf);
                }
            }
        }
    }
}

- BFS

package bfs;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int N, M, K;
    static int result = Integer.MIN_VALUE;
    static int tempResult = 0;

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int xPoint = Integer.parseInt(st.nextToken()) - 1;
            int yPoint = Integer.parseInt(st.nextToken()) - 1;

            map[xPoint][yPoint] = -1;
        }

        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {

                if (!visited[i][j] && map[i][j] == -1) {
                    tempResult += 1;
                    bfs_trash(i, j);

                    result = Math.max(tempResult, result);
                    tempResult = 0;
                }
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void bfs_trash(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Point poll = queue.poll();

            for (int i = 0; i < 4; i++) {
                int xf = poll.x + dx[i];
                int yf = poll.y + dy[i];

                if (xf >= 0 && yf >= 0 && xf < N && yf < M && !visited[xf][yf]) {
                    if (map[xf][yf] == -1) {
                        queue.add(new Point(xf, yf));
                        visited[xf][yf] = true;
                        tempResult += 1;
                    }
                }
            }
        }
    }
}