[백준] 1743 - 음식물 피하기

[문제링크]

1743번: 음식물 피하기

 

0. 가장 큰 음식물 덩어리의 크기 구하기

• 상하좌우로 연결되 있을 경우 한 덩어리로 본다

 

1. 음식물의 여부를 boolean 배열로 표현한다

 

2. 탐색 중 음식물 발견시, dfs 탐색으로 진입한다

• 이미 탐색한 음식물 제거 (현재 위치 false로 변경)
• 상하좌우 4방향 각각으로 음식물이 있으면 진행한다
• 최종적으로 연결된 모든 음식물을 지우고, 그 크기를 반환

 

3. 모든 음식물 덩어리중 가장 큰 값 유지, 출력

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int k = pint(st.nextToken());
		boolean[][]map = new boolean[n][m];
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			map[pint(st.nextToken())-1][pint(st.nextToken())-1]=true;
		}
		int ans=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j])ans=Math.max(ans, dfs(map,i,j));
			}
		}
		System.out.println(ans);
	}
	
	static int dfs(boolean[][]map, int i, int j) {
		int area=1;
		map[i][j]=false;
		if(i+1<map.length && map[i+1][j])area+=dfs(map,i+1,j);
		if(j+1<map[0].length && map[i][j+1])area+=dfs(map,i,j+1);
		if(i-1>=0 && map[i-1][j])area+=dfs(map,i-1,j);
		if(j-1>=0 && map[i][j-1])area+=dfs(map,i,j-1);
		return area;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과화면