백준 1743번 : 음식물 피하기

 문제

www.acmicpc.net/problem/1743

1743번: 음식물 피하기

1743 음식물 피하기

 

 구현 방법

 dfs/bfs를 통해 구현해줍니다.

들어가는 개수를 카운트 하고 끝날때마다 비교해서 최댓값을 구해줍니다.

 

 구현 코드

package BOJ.Silver;

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

public class BOJ1743_음식물피하기 {
	static int R, C, K, MAX, cnt;
	static int[][] map, deltas= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken()); // 쓰레기 개수
		map = new int[R][C];
		for (int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			map[r-1][c-1] = 1;
		}
		// 입력완료
		MAX = Integer.MIN_VALUE;
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (map[r][c]==1) {
					cnt = 1;
					map[r][c] = 0;
					dfs(r, c);
					MAX = Math.max(MAX, cnt); // 최댓값 구하기
				}
			}
		}
		System.out.println(MAX);
	}
	
	static void dfs(int r, int c) {
		for (int d=0;d<4;d++) {
			int nr = r+deltas[d][0];
			int nc = c+deltas[d][1];
			if (isIn(nr, nc) && map[nr][nc]==1) {
				cnt++;
				map[nr][nc]=0;
				dfs(nr, nc);
			}
		}
		return;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!