백준 1245번 : 농장 관리

 문제

www.acmicpc.net/problem/1245

1245번: 농장 관리

1245 농장 관리

 

 구현 방법

 농장에서 산봉우리를 찾아야하므로 전체를 탐색 해줍니다.

주변 8방을 탐색하여 자신보다 큰 높이가 있다면 flag = false, flag가 true

즉 자신보다 큰 높이가 없을 때만 산봉우리 카운트를 ++해줍니다.

주변이 같은 높이를 가진다면 같은 산봉우리로 인식하고 해당 위치도 dfs를 돌려야합니다.

 

* 주의할 점 *

주변을 탐색해서 같은 레벨일 때 꼭 방문체크를 해주셔야 합니다.

방문체크를 하지 않는다면 전체를 탐색하면서 다시 방문하게 되고 카운트를 또 세어줌으로써 값이 2배로 늘어납니다.

 

 구현 코드

package BOJ.Silver;

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

public class BOJ1245_농장관리 {
	static int R, C;
	static int[][] map, deltas= {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
	static boolean flag;
	static boolean[][] visit;
	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());
		map = new int[R][C];
		visit = new boolean[R][C];
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<C;c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		int ans = 0;
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (!visit[r][c]) {
					flag = true;
					dfs(r, c);
					if (flag) ans++;
				}
			}
		}
		System.out.println(ans);
	}
	
	static void dfs(int r, int c) {
		for (int d=0;d<8;d++) {
			int nr = r+deltas[d][0];
			int nc = c+deltas[d][1];
			if (isIn(nr, nc)) {
				if (map[r][c]<map[nr][nc]) flag = false;
				if (!visit[nr][nc] && map[r][c]==map[nr][nc]) { // 같은 높이라면
					visit[nr][nc] = true; // 방문체크 후
					dfs(nr, nc); // 탐색
				}
			}
		}
		return;
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!