[백준](Java) 2468 - 안전 영역
문제 링크
문제 풀이
비에 잠기는 범위를 제한 하기 위해
map에 값을 넣으면서 가장 낮은값과, 가장 높은값을 알아냈다.for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ map[i][j] = sc.nextInt(); minnum = Math.min(minnum, map[i][j]); maxnum = Math.max(maxnum, map[i][j]); } }
전체 큰 for문은 가장 낮은값부터, 가장 높은 값까지 반복하는 for문이며 그 안에서
물에 잠기는 지역의 값은 0으로 만들어주었다.for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(map[i][j]<=k){ map[i][j]=0; } } }
그리고 chk를 전부 false로 만들어주어 다시 bfs를 탐색하도록 만들었다.
for(int i=0; i<n; i++){ Arrays.fill(chk[i], false); }
그리고 다시 맵을 돌며 아직 물에 잠기지 않았으며, 방문하지 않은곳으로 bfs 탐색을 시작한다.
for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(!chk[i][j] && map[i][j]!=0){ bfs(i,j); } } }
bfs를 진행할때마다 해당 강수량일때의 안전한 지역을 나타내는 temp의 count가 올라가며
가장 안전한 지역이 많은 개수와 비교하며 그값을 answer로 하고
다시 temp를 초기화한다.
answer = Math.max(answer,temp); temp = 0;
코드
package bfs;
import java.util.*;
public class BJ2468 {
static int[][] map;
static boolean[][] chk;
static int temp =0;
static int n;
static int[] diry = {-1, 0, 1, 0}; //상 우 하 좌
static int[] dirx = {0, 1, 0, -1};
public static class Node {
int y;
int x;
public Node(int y, int x) {
this.y = y;
this.x = x;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int answer =1;
int minnum = Integer.MAX_VALUE;
int maxnum = Integer.MIN_VALUE;
n = sc.nextInt();
map = new int[n][n];
chk = new boolean[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
map[i][j] = sc.nextInt();
minnum = Math.min(minnum, map[i][j]);
maxnum = Math.max(maxnum, map[i][j]);
}
}
for(int k=minnum; k<=maxnum; k++){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(map[i][j]<=k){
map[i][j]=0;
}
}
}
for(int i=0; i<n; i++){
Arrays.fill(chk[i], false);
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(!chk[i][j] && map[i][j]!=0){
bfs(i,j);
}
}
}
answer = Math.max(answer,temp);
temp = 0;
}
System.out.println(answer);
}
public static void bfs(int y, int x){
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(y,x));
chk[y][x]=true;
while(!queue.isEmpty()){
Node now = queue.poll();
for(int i=0; i<4; i++){
int now_y = now.y+diry[i];
int now_x = now.x+dirx[i];
if(now_y>=0 && now_y<n && now_x>=0 && now_x<n){
if(!chk[now_y][now_x] && map[now_y][now_x]!=0){
queue.add(new Node(now_y,now_x));
chk[now_y][now_x] = true;
}
}
}
}
temp++;
}
}
Author And Source
이 문제에 관하여([백준](Java) 2468 - 안전 영역), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@courage331/백준Java2468-안전-영역저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)