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

www.acmicpc.net/problem/1743

1743번: 음식물 피하기

1. 음식물이 하나라도 있는 영역에 접근하면 dfs()재귀 함수에 빠진다.

2. 재귀함수내에서 음식물이 있을수록 계속 cnt++

3. 방금 cnt한 영역과 전체영역에서 가장 컸던 숫자를 비교 (Math.max)

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

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

	public static void main(String[] args) throws FileNotFoundException {
		//ㄴystem.setIn(new FileInputStream("sample_input.txt"));

		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();

		visit = new boolean[N + 1][M + 1];
		map = new int[N + 1][M + 1];
		// Arrays.fill(map, 0);

		for (int i = 0; i < K; i++) {
			int r = sc.nextInt();
			int c = sc.nextInt();
			map[r][c] = 1;
		}


		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {

				if (!visit[i][j] && map[i][j] == 1) {
					
					cnt = 1;
					visit[i][j] = true;
					dfs(i, j);
					ans = Math.max(cnt, ans);
					

				}
			}
		}

		System.out.println(ans);
	}

	public static void dfs(int row, int col) {

		//System.out.println("*" + row + "," + col + "//cnt : " + cnt);
		for (int i = 0; i < dx.length; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];

			if (nx < 1 || nx > N || ny < 1 || ny > M)
				continue;
			if (visit[nx][ny])
				continue;
			if (map[nx][ny] == 0)
				continue;

			visit[nx][ny] = true;
			cnt++;

			dfs(nx, ny);
			

		}

	}

}