자바(Java) 알고리즘 문제풀이 음식물 피하기 [백준 / DFS]

출처 - 구글 이미지

 

 

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

1743번: 음식물 피하기

 

 

풀이 코드

DFS 완전 탐색으로 풀이했다.

저번에 풀이했던 백준 1303 전쟁-전투 문제와 아주 유사한 문제이다. 어느 부분에서 쓰레기가 가장 많이 뭉쳐져있는지? 확인하는 문제.

역시 이중 for문을 사용해 방문하지 않았고 쓰레기가 있는 곳을 DFS() 재귀 호출을 사용하고 DFS 함수 내에서 방향 벡터를 사용해 쓰레기가 있고 방문하지 않은 부분이라면 쓰레기 개수인 변수 count 를 하나 씩 늘려주는 방식으로 풀이했다.

 

이전 전쟁-전투 문제에서도 언급했지만, 항상 count 변수를 0으로 할지, 1로 할지, 어느 부분에서 count 를 증가시키는지에 대해 유의하면서 풀이해야 한다. 마지막으로 Math.max() 함수를 사용해 쓰레기가 있는 어떤 부분에서 가장 많이 뭉쳐있는지 판단 후 출력하면 끝 !

package backjoonsliver.dfs;

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

public class 음식물_피하기_Review {
    static int n;
    static int m;
    static int k;
    static int count;
    static int answer;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] map;
    static boolean[][] visited;

    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][m];
        visited = new boolean[n][m];

        // 쓰레기 먼저 배치
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 1은 쓰레기, 0은 통로
            map[x - 1][y - 1] = 1;
        }

        // 쓰레기가 아닌 곳 통로로 배치
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] != 1) {
                    map[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    // 어느 부분이 제일 많이 뭉쳐있는지 확인하는 이런 문제 유형에서는 항상 count 초기 값을 유의하자.
                    // 쓰레기가 있을 때를 조건에 걸었기 때문에 무조건 쓰레기가 최소 한 개는 있는거니까 count = 1 초기화
                    count = 1;
                    DFS(i, j);
                    answer = Math.max(count, answer);
                }
            }
        }

        System.out.println(answer);
    }

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

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

            if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                count++;
                DFS(nx, ny);
            }
        }
    }
}