[백준 - Java] 1245번 : 농장 관리

문제

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

설명

BFS, DFS 두 가지 방법을 이용해 문제를 해결할 수 있다!

주의할 점

처음에 현재 높이보다 더 높은 봉우리를 만났을 때 해당 봉우리는 산봉우리가 될 수 없기 때문에 바로 false를 반환해 주었다.

바로 이렇게 false를 반환하고 while문 밑에서 return true를 해주었다.

for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
		if (!visited[i][j]) {
        	// 여기서 해당 봉우리에 대해 한 번 더 bfs를 돌게 됨
			if (bfs(i, j)) {
				answer++;
			}
		}
	}
}

// bfs 내의 코드
// 높이가 더 높은 경우
if (map[nx][ny] > map[x][y]) {
	return false;
}

그런데 이렇게 하면 해당 봉우리 전체의 크기를 알 수 없게 되어버려서 bfs를 돌리기 전 for문에서 또 해당 봉우리에 대해 bfs를 돌게 되고.. 결국 답이 이상하게 나와버린다..

그래서 flag 변수를 따로 두고 해당 높이보다 더 높은 경우 flag에 false를 저장하고 해당 봉우리 전체를 돌 수 있도록 수정했다!

소스코드

/**
 * 1245 농장 관리
 * https://www.acmicpc.net/problem/1245
 * 
 * @author minchae
 * @date 2024. 2. 26.
 */

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

public class Main {
	
	static class Pair {
		int x;
		int y;
		
		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	// 상하좌우, 대각선
	static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
	static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
	
	static int N, M;
	static int[][] map;
	
	static boolean[][] visited;
	static boolean isTop;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		visited = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int answer = 0;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visited[i][j]) {
					if (bfs(i, j)) {
						answer++;
					}
					
//					isTop = true;
//					
//					dfs(i, j);
//					
//					if (isTop) {
//						answer++;
//					}
				}
			}
		}
		
		System.out.println(answer);
	}
	
	private static boolean bfs(int x, int y) {
		Queue<Pair> q = new LinkedList<>();
	
		q.add(new Pair(x, y));
		visited[x][y] = true;
		
		int height = map[x][y];
		
		boolean flag = true;
		
		while (!q.isEmpty()) {
			Pair cur = q.poll();
			
			for (int i = 0; i < 8; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				
				if (!isRange(nx, ny)) {
					continue;
				}
				
				// 현재 높이보다 더 높은 봉우리가 있는 경우 산봉우리가 될 수 없음
				if (map[nx][ny] > map[x][y]) {
					flag = false; // 바로 false를 반환해버리면 해당 산봉우리 전체를 구할 수가 없기 때문에 flag 변수 사용
				}
				
				if (!visited[nx][ny] && map[nx][ny] == map[x][y]) {
					q.add(new Pair(nx, ny));
					visited[nx][ny] = true;
				}
			}
		}
		
		return flag;
	}
	
	private static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (!isRange(nx, ny)) {
				continue;
			}
			
			// 현재 높이보다 더 높은 봉우리가 있는 경우 산봉우리가 될 수 없음
			if (map[nx][ny] > map[x][y]) {
				isTop = false;
			}
			
			if (!visited[nx][ny] && map[nx][ny] == map[x][y]) {
//				visited[nx][ny] = true;
				dfs(nx, ny);
			}
		}
		
		return;
	}
	
	private static boolean isRange(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}

}

GITHUB

https://github.com/MinchaeKwon/BOJ/blob/master/BOJ%1245/src/Main.java