[BOJ2468/JAVA] 안전 영역

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

2468번: 안전 영역

 

문제

 

 

풀이

해당문제는 BFS로 풀었던 완전탐색문제이다. 물에 잠기지 않는 안전한 영역의 최대 개수를 구해야한다.

BFS로 탐색하면서 일정높이보다 높은 영역의 개수를 count를 세야한다. 이때 높이를 다 설정해가면서 최댓값을 계속해서 업데이트를 해주어야한다.

 

1. 입력값을 다 받으면서 영역의 가장 높은 길이를 구해준다.

(1~100까지 다 최댓값을 구하는 것보다는 입력값의 가장 높은 길이를 구해서 그만큼만 구하는 것이 훨씬 효율적!)

2. 만약 가장 높은 길이가 9이면 for문을 돌면서 길이를 점차 늘리면서 count값을 세준다,

3. count를 셀 때마다 높이에 따른 안전한 영역의 최댓값을 구해준다.

4. 최댓값을 출력해주면 끝!

 

나는 계속 왜 답이 다르게 나오지라고 생각했는데 높이를 다르게 하고 count를 셀 때마다 방문값과 count를 초기화 시켜줘야한다!

이것을 놓쳐서 계속 다른 값이 나왔던...

 

코드

package Week16;

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 BOJ2468 {

	static int n;
	static int map[][];
	static int dx[] = {1,-1,0,0};
	static int dy[] = {0,0,1,-1};
	static boolean visited[][];
	static int cnt=0;
	static int answer=0;
	static int max=0;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		visited = new boolean[n][n];
		map = new int[n][n];
		
		int height = 0;
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]>height) {
					height=map[i][j];
					// 웅덩이 중 가장 높은 웅덩이 찾기
				}
			}
		}
		for(int h=0;h<height;h++) {
			visited = new boolean[n][n];
			cnt=0;
			// 다시 초기화
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(!visited[i][j] && map[i][j] > h) {
						bfs(i,j,h);
						cnt++;
					}
				}
			}
			max=Math.max(cnt, max);
		}
		
		System.out.println(max);
	}
	
	public static void bfs(int x,int y, int h) {
		
		Queue<Node> q = new LinkedList<>();
		visited[x][y]=true;
		q.offer(new Node(x,y));
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			for(int i=0;i<4;i++) {
				int new_x = node.x+dx[i];
				int new_y = node.y+dy[i];
				
				if(new_x>=0 && new_y >= 0 && new_x<n && new_y<n) {
					if(!visited[new_x][new_y] && map[new_x][new_y] > h) {
						q.offer(new Node(new_x,new_y));
						visited[new_x][new_y]=true;
					}
				}
			}
		}
	}
	
	public static class Node {
		int x;
		int y;
		
		public Node(int x,int y) {
			this.x=x;
			this.y=y;
		}
	}

}