DFS ( 1303 번과 동일 )

백준 1743번을 DFS 를 이용해 Java 로 풀어봤다. 문제를 읽고 그림을 그려보자마자 1303번과 동일한 원리로 풀면 되겠다는 것을 알 수 있었다. 진짜 똑같았다는 사실

주어진 예시를 직접 그려보면 위와 같이 빨간 느낌표가 음식물 쓰레기의 위치고 나머지 위치들은 비어있는 그림이 나온다.
for문 을 통해 쓰레기가 있는 자리에서만 DFS 를 돌려주면 된다. 그 결과로 나온 값들을 이전의 값들과 비교해서 더 큰 녀석을 채택해주며 map 을 다 돌고 나면 우리가 원하는 답이 나와있을 것이다.

1303번과 워낙 동일한 문제라서 짧게 쓰고 끝내겠다.

아래는 제출한 코드다.

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

public class boj1743 {
    static int N,M,K;
    static int[][] map;
    static boolean[][] visited;
    static int[] directionRow = { -1, 1, 0, 0}; // 상하좌우 순서
    static int[] directionCol = { 0, 0, -1, 1};
    static int answer;
    static int count;

    static void dfs(int row, int col){
        visited[row][col] = true;
        count += 1;

        for(int i=0; i<4; i++){
            int newRow = row + directionRow[i];
            int newCol = col + directionCol[i];

            if(newRow<1 || N<newRow || newCol<1 || M<newCol)
                continue;
            if(map[newRow][newCol]==0 || visited[newRow][newCol])
                continue;

            dfs(newRow, newCol);
        }
    }

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

        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        K = Integer.parseInt(stk.nextToken());
        map = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];

        for(int i=0; i<K; i++){
            stk = new StringTokenizer(bfr.readLine());
            int row = Integer.parseInt(stk.nextToken());
            int col = Integer.parseInt(stk.nextToken());
            map[row][col] = 1;
        }

        for(int row=1; row<=N; row++){
            for(int col=1; col<=M; col++){
                if(map[row][col]==1 && !visited[row][col]){
                    count = 0;
                    dfs(row, col);
                    answer = Integer.max(count, answer);
                }
            }
        }

        bfw.write(String.valueOf(answer));
        bfw.close();
    }
}