[BaekJoon] 1743번 음식물 피하기 (Java) 문제 풀이 [Sliver 1]

문제

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

1743번: 음식물 피하기

 

어떻게 풀 것인가?

DFS를 이용한 탐색을 사용하였다.

추후에 포스팅을 통해서 설명할테지만, 범위가 크다면 StackOverFlow를 피하기 위해서 재귀보다는 Stack을 이용한 DFS 방식을 사용하는 것을 선호한다.

 

DFS를 이용하여 음식물 쓰레기의 영역 범위를 구하고 가장 큰 값을 반환하면 된다. 이는 코드를 통해서 보는 것이 훨씬 쉽다.

 

풀면서 놓쳤던점

최근 들어서 반복적인 DFS 연습을 통해서 이번 문제에서는 실수한 것이 없었다.

 

이 문제를 통해 얻어갈 것

DFS 활용

 

내 코드 

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

public class Main {
    static int N;
    static int M;
    static int K;
    static int[][] map;

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

    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 + 1][M + 1];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map[r][c] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] == 1) DFS(i, j);
            }
        }
        System.out.print(max);

    }

    private static void DFS(int x, int y) {
        Stack<ColRow> stack = new Stack<>();
        stack.push(new ColRow(x, y));
        map[x][y] = 0;
        int num = 1;
        while (!stack.isEmpty()) {
            ColRow current = stack.pop();
            int cx = current.x;
            int cy = current.y;

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if (range(nx, ny) && map[nx][ny] == 1) {
                    stack.push(new ColRow(nx, ny));
                    map[nx][ny] = 0;
                    num++;
                }
            }
        }
        if (max < num) max = num;
    }

    private static boolean range(int x, int y) {
        return ((x >= 1) && (x <= N)) && ((y >= 1) && (y <= M));
    }

}

class ColRow {
    int x;
    int y;

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

 

참고

X