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

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

1743번: 음식물 피하기

 

1743, 음식물 피하기

📌 [ 난이도 : 실버 1 ]

이번 문제는 DFS & BFS 를 사용해서 풀이했다.

두 방식에 시간과 메모리 차이는 크게 없는 거 같지만 가장 중요한 개념이라고 생각하기에

항상 두 방식으로 풀어보길 권장한다.

 

📚 Process

초기화 및 선언

: 항상 배열을 만들어 줄 때 x, y에 대한 구분이 헷갈리는데 명확하게 하지 않으면 index 에러가 발생할 수 있으니

주의하길 바란다

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
static int[][] area;
static boolean[][] visit;
static int N, M, K, max, trash;
static Queue<Integer> q = new LinkedList<>();

static void input() throws IOException{
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    area = new int[N][M];
    visit = new boolean[N][M];

    while (K-- > 0) {
        StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
        area[Integer.parseInt(st1.nextToken()) - 1][Integer.parseInt(st1.nextToken()) - 1] = 1;
    }
}

 

탐색

: BFS & DFS 의 개념은 깊게 설명하지 않겠다. 처음부터 순회하며 쓰레기가 있는 구간이 확인되면 그 구간을 기준으로 붙어있는 쓰레기를 모두 탐색하며 넓이를 구하고, 최대값을 갱신해주면 되는 문제이다.

 

✅ 전체 코드

📎 DFS 풀이

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    static int[][] area;
    static boolean[][] visit;
    static int N, M, K, max, trash;

    static void input() throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        area = new int[N][M];
        visit = new boolean[N][M];

        while (K-- > 0) {
            StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
            area[Integer.parseInt(st1.nextToken()) - 1][Integer.parseInt(st1.nextToken()) - 1] = 1;
        }
    }

    static void pro() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (area[i][j] == 1 && !visit[i][j]) {
                    trash = 0;
                    dfs(j, i);
                    max = Math.max(max, trash);
                }
            }
        }

        System.out.println(max);
    }

    static void dfs(int x, int y) {
        trash++;
        visit[y][x] = true;

        for (int k = 0; k < 4; k++) {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];

            if (nx < 0 || ny < 0 || ny >= N || nx >= M)
                continue;
            if (visit[ny][nx])
                continue;
            if (area[ny][nx] != 1)
                continue;

            dfs(nx, ny);
        }
    }

    public static void main(String[] args) throws IOException{
        input();
        pro();
    }
}

 

📎 DFS 풀이

 

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    static int[][] area;
    static boolean[][] visit;
    static int N, M, K, max, trash;
    static Queue<Integer> q = new LinkedList<>();

    static void input() throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        area = new int[N][M];
        visit = new boolean[N][M];

        while (K-- > 0) {
            StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
            area[Integer.parseInt(st1.nextToken()) - 1][Integer.parseInt(st1.nextToken()) - 1] = 1;
        }
    }

    static void pro() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (area[i][j] == 1 && !visit[i][j]) {
                    trash = 0;
                    bfs(j,i);
                    max = Math.max(max, trash);
                }
            }
        }
    }

    static void output() {
        System.out.println(max);
    }

    static void bfs(int x, int y) {
        trash++;

        visit[y][x] = true;
        q.add(x);
        q.add(y);
        while(!q.isEmpty()) {
            int tx = q.poll();
            int ty = q.poll();

            for(int k=0; k<4; k++) {
                int nx = tx + dir[k][0];
                int ny = ty + dir[k][1];

                if (nx < 0 || ny < 0 || ny >= N || nx >= M) continue;
                if (visit[ny][nx]) continue;
                if (area[ny][nx] != 1) continue;

                q.add(nx);
                q.add(ny);
                
                trash++;
                visit[ny][nx] = true;
            }
        }
    }

    public static void main(String[] args) throws IOException{
        input();
        pro();
        output();
    }
}

65074446 - BFS

65073563 - DFS