BFS

백준 2468번을 자바를 이용해 풀어보았다.
문제 링크 첨부한다.
https://www.acmicpc.net/problem/2468

---

강수량별로 결과 구해주기

비가 오지 않은 경우부터 모든 건물이 다 잠길 높이까지 비가 온 경우들을 모두 돌면 된다. 각 강수량별로 BFS를 이용해서 결과를 구했다.

가장 처음에 문제 입력값을 받을 때 가장 높은 높이를 저장해두고 h=0 부터 h=max까지 다 돌면 되는 것이다.

---

map 재구성

문제 입력값의 map을 그대로 사용하지 않고 각 강수량별로 잠겼는지 잠기지 않았는지만이 중요한 정보이기 때문에 이를 기준으로 새로운 map 을 할당한다. 잠겼으면 0, 잠기지 않았으면 1로 설정해줬다.
이에 따른 코드는 다음과 같다.

int[][] map = new int[N][N]; // 새로운 map 할당
boolean[][] visited = new boolean[N][N];
for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
		map[i][j] = (org[i][j]<=h) ? 0 : 1; // org는 입력받은 map 정보

---

안전 영역 개수 세기

map의 원소가 0인 곳은 지나치고 1인 곳에서는 탐색을 시작한다. 탐색을 시작할 때마다 cnt값을 1씩 늘려주면 해당 강수량 탐색 차례에서 몇 개의 영역이 존재하는지 확인할 수 있다. 이를 코드로 옮기면 다음과 같다.

for(int i=0; i<N; i++){
	for(int j=0; j<N; j++){
		if(map[i][j]==0)    continue; // 잠겼으면 패스
		if(visited[i][j])   continue; // 이미 방문했으면 패스

		cnt++;
       
       		... // 연결된 영역 처리해주는 과정
       
      
		}
	}

---

아래는 내가 제출한 전체 코드다.

import java.util.*;

public class boj2468 {

   static int answer = 0;
   static int N;
   static int[][] dir = {{-1,0}, {1,0}, {0,-1}, {0,1}}; // 상 하 좌 우

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       N = sc.nextInt();

       int maxHeight = 1;
       int[][] map = new int[N][N];
       for (int i = 0; i < N; i++) {
           for (int j = 0; j < N; j++) {
               map[i][j] = sc.nextInt();
               maxHeight = Math.max(map[i][j], maxHeight);
           }
       }

       for (int h = 0; h <= maxHeight; h++) bfs(map, h);

       System.out.println(answer);
   }

   static void bfs(int[][] org, int h) {
       int cnt = 0;
       int[][] map = new int[N][N];
       boolean[][] visited = new boolean[N][N];
       for (int i = 0; i < N; i++)
           for (int j = 0; j < N; j++)
               map[i][j] = (org[i][j]<=h) ? 0 : 1;

       Queue<int[]> q = new LinkedList<>();
       for(int i=0; i<N; i++){
           for(int j=0; j<N; j++){
               if(map[i][j]==0)    continue; // 잠겼으면 패스
               if(visited[i][j])   continue; // 이미 방문했으면 패스

               cnt++;

               q.add(new int[]{i, j});
               visited[i][j] = true;

               while(!q.isEmpty()){
                   int[] pos = q.poll();
                   int curRow = pos[0];
                   int curCol = pos[1];

                   for(int d=0; d<4; d++){
                       int nxtRow = curRow + dir[d][0];
                       int nxtCol = curCol + dir[d][1];

                       if(!isInMap(nxtRow, nxtCol))    continue;
                       if(visited[nxtRow][nxtCol]) continue;
                       if(map[nxtRow][nxtCol]==0)  continue; // 잠겼으면 더이상 진출 X

                       q.add(new int[]{nxtRow, nxtCol});
                       visited[nxtRow][nxtCol] = true;
                   }
               }
           }
       }

       answer = Math.max(answer, cnt);
   }

   static boolean isInMap(int r, int c){
       return r>=0 && r<N && c>=0 && c<N;
   }
}

---

마치며

정말 기본적인 BFS 문제였다. 그런데 한 번 틀렸다. 비가 안 오는 경우는 없다고 생각하고 map의 가장 낮은 높이부터 h값을 설정하고 돌렸더니 test case 는 통과하지만 제출하니까 틀리는 경우가 있었나보다. 가끔 문제의 조건을 내 맘대로 바꿔서 푸는 경우가 있다. 모든 제한 조건을 다 제대로 지키고 있는지 꼼꼼하게 확인하는 습관을 좀 길러야겠다.