백준 1743 자바 풀이

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

1743번: 음식물 피하기

DFS를 통해서 풀어보자.

visit 체크를 하며 방문하지 않은 정점에 대해 방문하고 이어져 있는 정점의 개수를 세도록 했다. 그 중 제일 많은 것에 대해 출력한다.

 

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

public class bj1743_인접행렬 {

    static int N, M, K;
    static int cnt;
    static int[][] map;
    static boolean[][] visit;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };

    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];
        visit = new boolean[N][M];

        int answer = 0;
        String[] tmp;

        //이중 포문 안돌리려고 노력함..
        for(int i = 0; i < K; i ++) {
            tmp = br.readLine().split(" ");
            map[Integer.parseInt(tmp[0]) - 1][Integer.parseInt(tmp[1]) - 1] = 1;
        }

        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < M; j ++) {
                if(!visit[i][j] && map[i][j] == 1) {
                    cnt = 0;
                    DFS(i, j);
                    answer = Math.max(answer, cnt);
                }
            }
        }

        System.out.println(answer);

    }

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

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

            if(nx < N && nx >= 0 && ny < M && ny >= 0 && !visit[nx][ny] && map[nx][ny] == 1) {
                DFS(nx, ny);
            }
        }
    }
}