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

1. 문제

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

1743번: 음식물 피하기

 

 

 

2. 풀이과정

이 문제는 dfs나 bfs 둘 중 하나로 풀 수 있을 것 같은데, dfs를 선택한 이유는 n, m의 최대 크기가 100으로 작은 편이라 stack이 최대 100x100개정도 밖에 안 쌓이며, 코드도 더 짧기 때문이다.

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

public class boj1743 {
	static int n, m;
	static boolean map[][];
	
	public static int dfs(int x, int y) {
		int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
		int cnt = 0;
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx<=0 || nx>n || ny<=0 || ny>m || !map[nx][ny]) {continue;}
			map[nx][ny] = false;
			cnt += dfs(nx, ny)+1;
		}
		return cnt;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int trashes[][] = new int[k][2];
		map = new boolean[n+1][m+1];
		for(int i=0; i<k; i++) {
			st = new StringTokenizer(br.readLine());
			trashes[i][0] = Integer.parseInt(st.nextToken());
			trashes[i][1] = Integer.parseInt(st.nextToken());
			map[trashes[i][0]][trashes[i][1]] = true;
		}
		
		int result = 0;
		for(int[] trash : trashes) {
			if(map[trash[0]][trash[1]]) {
				result = Math.max(result, dfs(trash[0], trash[1]));
			}
		}
		System.out.println(result);
	}

}

 

결과

풀이시간 : 15분