[DFS] 백준 - 1743번: 음식물 피하기 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

1743번: 음식물 피하기

 

 

문제는 다음과 같다.

그냥 가장 큰 음식물의 크기를 구하는 것이다.

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 boolean[][] map;
    static boolean[][] visited;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int max;
    static int count;

    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());
        int k = Integer.parseInt(st.nextToken());

        map = new boolean[n][m];
        visited = new boolean[n][m];
        max = 0;
        count = 0;

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            map[a][b] = true;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && map[i][j]) {
                    dfs(i, j);
                    max = Integer.max(max, count);
                    count = 0;
                }
            }
        }

        System.out.println(max);
    }

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

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

            if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                if (!visited[nowX][nowY] && map[nowX][nowY]) {
                    dfs(nowX, nowY);
                }
            }
        }
    }
}

 

슬슬 DFS 공부는 여기까지 하고 BFS를 공부해봐야겠다..!