백준1245 농장 관리 (Java)

1. 문제 링크

1245번: 농장 관리

 

2. 문제 및 입출력예제

 

3. 문제 풀이

BFS로 하니까 바로 틀렸습니다 뜨거나 2%에서 떠서 DFS로 갈아탔다.

dfs로 진행하면서 8방 탐색을 하는데 더 높은 숫자가 나온다면 isPick을 false로 리턴한다.

끝까지 진행해서 true가 return되는 경우에 꼭대기의 수를 1만큼 늘린다.

 

 

4. 코드

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

public class Main {
	static int N, M, map[][], cnt;
	static boolean[][] visit;
	static boolean isPick;
	static int[] dx = {0,0,-1,1, -1,1,1,-1};
	static int[] dy = {-1,1,0,0, 1,1,-1,-1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		map = new int[N][M];
		visit = new boolean[N][M];
		for(int i=0;i<N;i++) {
			split = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(split[j]);
			}
		}		
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(!visit[i][j]) {
					isPick = true;
					dfs(i, j);
					if(isPick) {
						cnt++;
					}
				}
			}
		}
		
		System.out.println(cnt);
	}
	private static void dfs(int i, int j) {
		visit[i][j] = true;
		for(int d=0;d<8;d++) {
			int x = i+dx[d];
			int y = j+dy[d];
			if(x<0 || x>=N || y<0 || y>=M) {
				continue;
			}
			if(map[x][y] > map[i][j]) {
				isPick = false;
			}
			else if(!visit[x][y] && map[x][y] == map[i][j]) { //여기서 방문 확인을 해야 isPick에 영향을 안 주네
				dfs(x, y);
			}
		}
		
	}
}