[Java] BFS 두 문제 비교.( 미로찾기 + 안전영역 찾기 )

지금까지 내가 BFS 로 문제를 푼  두 문제를 서로 연결해서

문제 해결에 필요한 사고방식과 논리를 완전히 정리할까 한다.

이러한 정리를 통해서 다른 문제에도 확장해서 쓸 수 있도록 

외우는 포인트와 사고 공식도 같이 정리할 것이다. 

---

첫 번째 문제  : 갈 수 있는 길을 통해 목적지 도달하기. 

 0   1   2   3
  +---+---+---+---+
0 | S | ■ | O | O |
  +---+---+---+---+
1 | O | O | O | ■ |
  +---+---+---+---+
2 | ■ | ■ | O | ■ |
  +---+---+---+---+
3 | O | O | O | G |
  +---+---+---+---+
  
  (0,0)에서 출발하여 (3, 3)인 도착점으로 가야한다. 
  조건은 눈을 감고 한 칸씩만 갈 수 있다.
  그래서 갈 수 있는 길인지, 먼저 확인하고 하나씩 줄 세워서 이동해야 한다.

 

 

정답 코드 

package -

import java.util.*;

public class MazeSolver {
  
   static int N = 4; 
   static int[][] maze = {
      {1, 0, 1, 1},
      {1, 1, 1, 0},
      {0, 0, 1, 0},
      {1, 1, 1, 1}
   }
      // 상, 우, 하, 좌
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        boolean result = bfs(0, 0);
        System.out.println(result ? "미로 탈출 성공" : "미로 탈출 실패!");
    }
    
    
    static boolean bfs(int startX, int startY){
       Queue <int[]> queue = new LinkedList<>();
       boolean[][] visited = new boolean[N][N];
       
       queue.add(new int[]{startX, startY});
       visited[startX][startY] = true;
       
       while (!queue.isEmpty()){
          int[] current = queue.poll();
          int x = current[0];
          int y = current[1];
          
          if (x == N-1 && y == N-1) return true;
          
          for (int i = 0; i < 4 ; i++) {
              int nx = x + dx[i];
              int ny = y + dy[i];
              
              if (nx >= 0 && nx < N && ny >= 0 && ny < N
                  && !visited[nx][ny] && maze[nx][ny] == 1) {
                  queue.add(new int[]{nx,ny});
                  visited[nx][ny] = true;
                  }
          }
       }
       return false; // 도착하지 못함
    }
  
}

두 번째 문제  : 정수 행렬에서 안전 영역 찾기

 

문제 설명: 

N×N 크기의 정수 행렬이 있다.

각 칸에는 그 지점의 높이가 적혀 있다.

비가 내려 특정 높이 이하의 모든 지점이 물에 잠긴다고 가정할 때,

물에 잠기지 않는 안전한 영역의 개수를 구하는 프로그램을 작성해라.

 

안전한 영역이란 물에 잠기지 않은 지점들이 상하좌우로 연결된 영역을 의미한다.

 

입력:

• 첫 번째 줄에 행렬의 크기 N이 주어진다. (1 ≤ N ≤ 100)
• 다음 N개 줄에는 각 지점의 높이가 주어진다. (1 ≤ 높이 ≤ 100)

출력:

물에 잠기는 높이별로 안전한 영역의 최대 개수를 출력한다.

 

 

높이 정보가 주어진 지도에서, 특정 비 높이 이하의 칸은 물에 잠긴다고 할 때, 물에 잠기지 않고 연결된 안전 영역의 개수를 구하라. 
-> 높이별로 지도를 BFS 탐색하여
-> 연결된 안전 영역의 수를 세고, 그 중 가장 큰 값을 출력!

정답코드 

package -

import java.util.*;

public class SafeZone {
  
  // 방향 배열 : 상, 우, 하, 좌
  static int[] dx = {-1, 0, 1, 0};
  static int[] dy = {0, 1, 0, -1};
  
  // 프로그램의 시작점, 여기서 입력 받고 전체 로직을 실행 - 전역 변수 선언
  static int N; // 지도의 크기
  static int[][] map; // 지도의 높이 정보
  static boolean[][] visited; // BFS에서 방문 여부 체크
  
  public static void main(String[] args) {
      
      // 입력 - 지도 크기 및 map 값 입력에 사용
      Scanner sc = new Scanner(System.in);
      N = sc.nextInt(); // 지도 크기(N * N)를 설정, 이후 2차원 배열 생성시 사용됨.
      
      
      map = new int[N][N]; // 2차원 배열 선언, 변수 초기화. map은 각 칸의 높이 저장. 
      int maxHeight = 0; // 입력 중 가장 높은 지점을 기억. 이건 높이별 시뮬레이션 범위 지정에 사용됨
      
      // 각 칸마다 다른 높이 입력 받기, 이후 비 높이 범위를 정하는데 필요
      for (int i = 0; i < N; i++) {
          for (int j = 0; j < N ; j++) {
              // map[i][j]에 입력 저장하고 동시에 maxHeight 갱신
              map[i][j] = sc.nextInt();
              maxHeight = Math.max(maxHeight, map[i][j]);
          }
      }
      // 각 높이에서 참색한 safe zone 중 최대값 저장용
      int maxSafeZones = 0;
      
      // 비의 높이를 0부터 maxHeight까지 모두 시뮬레이션 - 조건에 따라 잠기지 않은 지역 판단 기준으로 사용됨
      for (int height = 0; height <= maxHeight; height++) {
          visited = new boolean[N][N]; // 현재 height 시뮬레이션 기준 방문 체크
          int safeZones = 0; // 현재 높이에서의 안전 영역 개수
          
          // 모든 칸을 순회하며 안전 영역의 시작점을 찾기 위함
          for (int i = 0; i < N; i++) {
              for (int j = 0; j < N; j++) {
                  // 방문 안 했고, 물에 잠기지 않은 칸이라면 bfs()탐색으로 연결된 영역 모두 방문 처리
                  if (!visited[i][j] && map[i][j] > height) {
                      bfs(i, just, height);
                      safeZones++; // 덩어리 한개 발견!
                  }
              }
          }
          // 현재 height에서 찾은 safe zone 개수가 최대이면 갱신
          maxSafeZones = Math.max(maxSafeZones, safeZones);
      }
      
      System.out.println(maxSafeZones);
  }
  // 이제 BFS 함수 들어가자
  // startX,startY에서부터 시작하는 안전 영역 전체를 탐색 - main에서 영역 찾을 때 호출됨
  static void bfs(int starX, int starY, int height) {
  
      
      Queue<int[]> queue = new LinkedList<>();
      queue.offer(new int[]{startX, startY}); //큐에 시작점 추가
      visited[startX][startY] = true; // 방문 체크
      
      // 큐에서 하나 꺼내서 현재 좌표 저장
      while (!queue.isEmpty()){
         int[] current = queue.poll();
         int x = current[0];
         int y = current[1];
         
         // 상우하좌 방향으로 다음 칸 확인
         for (int i = 0; i < 4; i++) {
             int nx = x + dx[i];
             int ny = y + dy[i];
             
             
             // 범위 안에 있고 방문하지 않았고 물에 잠기지 않았으면 큐에 넣고 방문 처리
             if (nx >= 0 && nx < N && ny >= 0 && ny < N
                 && !visited[nx][ny] && map[nx][ny] > height) {
                 queue.offer(new int[]{nx, ny});
                 visited[nx][ny] = true;
                 }
         }
      }
  }
}

 

두 번째 문제의 전체 논리 흐름 요약!

1. 입력 : N*N 정수 행렬(map)을 입력 받고, 가장 높은 높이(maxHeight)도 구함

2. 반복 : 비의 높이(height)를 0부터 maxHeight까지 하나씩 바꿔가며 반복

서로 상하좌우로 연결된 블럭은 하나의 안전 영역(덩어리)로 센다.
그래서 비의 높이가 높을수록 안전 영역이 많은것이 아니라
비의 높이에 따라 상하좌우 연결되는 덩어리의 개수가 달라지기 때문에
이렇게 반복하여 덩어리 즉, 안전 영역 개수가 어떤 높이에서 가장 많은지를 세는 것이다. 

3. BFS: 현재 높이에서 물에 잠기지 않은 안전 영역을 BFS로 탐색

4. 영역 수 세기 : 각 height마다 안전 영역의 개수(safeZones)를 세고 최댓값 저장

5. 출력 : 가장 많은 안전 영역 개수를 출력. 

---

1.  BFS 두 문제의 공통점과 차이점

항목	미로 탈출	안전 영역
목표	(0,0) → (N-1,N-1) 도달 여부	물에 잠기지 않은 “안전 영역”의 개수
방식	BFS로 한 번만 탐색	BFS를 여러 번 돌려서 “여러 영역”을 셈
공통점	방향 배열 사용, 큐 사용, 방문 체크, BFS 구조 동일
차이점	목적지 도달이면 끝	높이마다 반복해서 영역 개수 셈
조건	maze[nx][ny] == 1	map[nx][ny] > 물높이(height)

 

---

2.1 첫 번째 문제에서 사용된 컴퓨터 사고방식 핵심 3가지

 

 2.1.1 상태표현

미로를 2차원 배열로 표현(maze[x][y])

방문 여부는 visited[x][y]로 표현

Queue에 좌표 [x, y]를 넣으며 현재 상태를 저장

 

 2.1.2 경로 탐색 (탐색 알고리즘 적용)

BFS를 사용해 네 방향(상하좌우)으로 갈 수 있는지 반복 확인

먼저 도달 가능한 위치부터 넓게 퍼지듯이 탐색.

 

 2.1.3 종료 조건 설정

도착점 (N-1, N-1)에 도달하면 즉시 true 반환

큐가 모두 비었는데 도착점에 도달 못하면 false 반환

 

---

2.2 두번째 문제에서 사용된 컴퓨터적 사고방식 핵심 3가지

 

 2.2.1 완전 탐색(Brute Force )

- 모든 높이(0부터 최고 높이까지)를 하나하나 다 시험해봄

- 높이마다 BFS로 전체 영역을 새로 탐색

 

 2.2.2 BFS (너비 우선 탐색)

- 각 안전한 영역은 연결된 칸들의 집합이므로 BFS로 연결된 칸들을 한 번에 탐색

- 탐색이 한 번 끝나면 "영역 1개 발견"

 

 2.2.3 시뮬레이션

- 비가 왔을 때 상황을 가정해서 시뮬레이션하는 문제

- map 배열은 바꾸지 않고, visited와 height로 상태를 시뮬레이션

 

---

3.1 첫 번째 문제의 사고 흐름 정리

  3.1.1 미로가 주어졌을 때 어떻게 탐색할까? - 상하좌우로 이동 가능함

  3.1.2 어디서 시작하고 어디까지 가야 하지? - (0,0)에서 (N-1, N-1)까지 도달해야 함

  3.1.3 이미 갔던 칸은 다시 가지 않게 하려면? - visited[x][y] 배열 사용

  3.1.4  어떤 순서로 칸들을 확인하지? - BFS를 사용하여 가까운 칸부터 탐색

  3.1.5 도착지에 도달하면?-> 탐색 종료하고 true 반환

 

3.2 두번째 문제의 사고 흐름 정리(생각 순서)

 3.2.1 "비가 얼마나 올까" -> 모든 높이를 다 시도해보자.

 3.2.2 "물이 이만큼 차면 어디가 잠길까" -> map[x][y] <= height면 잠김. 

 3.2.3 "잠기지 않은 칸들은 연결돼 있을까" -> 상하좌우 탐색 필요.

 3.2.4 "하나의 덩어리를 어떻게 찾지?" -> BFS/DFS로 덩어리 하나를 찾자!

 3.2.5 "이걸 높이별로 반복하면 되겠네!"

 

 

---

4.1 첫 번재 문제의 수학적 사고(그래프 이론 기반)

 4.1.1 2차원 배열은 그래프의 형태로 모델링 가능

 4.1.2 각 칸은 노드, 상하좌우는 간선

 4.1.3 BFS는 그래프에서 최단 경로를 찾는 데 최적화된 알고리즘

 4.1.4 출발점부터 간선 하나씩 타면서 퍼져나가는 방식으로 도착점에 가장 먼저 도달하는 경로를 찾음

 

4.2 두 번째 문제의 수학적 사고 (그래프 이론 기반)

 4.2.1 2차원 배열은 그래프처럼 연결된 정점의 집합

 4.2.2 각 칸은 정점, 상하좌우는 간선

 4.2.3 "물에 잠기지 않은 칸"만 남긴 그래프를 만들고, 그 안에서 연결된 컴포넌트 개수를 구하는 문제!

 

---

5.1 첫 번째 문제의 코드 외우기 포인트 요약

 

5.1.1 방향 배열- 상우하좌 순서

int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

 

 

 

5.1.2 자료 준비 - 줄(Queue)과 발자국 배열 만들기

Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[N][N];

 

 

 

5.1.3 시작점 큐에 추가 - 출발점은 큐에 넣고, 방문 표시

queue.add(new[]{startX,startY});
visited[startX][startY] = true;

범위 안이고, 방문 안 했고, 길이면 => 큐에 추가 + 방문 표시

 

 

 

5.1.4 큐가 빌 때까지 BFS 탐색 - 줄에서 꺼내고, 도착했으면 true

while (!queue.isEmpty()) {
   int[] current = queue.poll();
   int x = current[0];
   int y = current[1];
   
   if (x == N -1 && y = N -1) return true;

 

 

 

5.1.5 네 방향으로 이동 - 범위 안이고, 방문 안 했고, 길이면 -> 큐에 추가 + 방문 표시

for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    
    if (nx>=0 && nx < N && ny >= 0 && ny < N
        && !visited[nx][ny] && maze[nx][ny] ==1){
        queue.offer(new int[]{nx,ny});
        visited[nx][ny] = true;
        }
    }
  }

 

 

5.1.6 다 돌았는데 도착 못하면 false

return false;

---

5.2 두 번째 문제의 코드 외우기 포인트 요약

 

 5.2.1 방향 배열 - 상, 우, 하, 좌 순서대로 움직일 수 있게 설정!

x↓   y→
    0   1   2   3
  +---+---+---+---+
0 |   |   |   |   |
  +---+---+---+---+
1 |   |   |   |   |
  +---+---+---+---+
2 |   |   |   |   |
  +---+---+---+---+
3 |   |   |   |   |
  +---+---+---+---+


//          상  하  우  좌
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

 

 

 5.2.2 높이별 전체 반복

for (int height = 0; height <= maxHeight; height++) {
    visited = new boolean[N][N];
    safeZones = 0;
    
    // 전체 map 탐색해서 아직 방문 안 했고 물에 안 잠긴 칸에서 BFS
}

각 높이마다 새로 visited 초기화
한 칸이라도 BFS 시작하면 safeZone++

 

 

5.2.3 BFS 구조는 미로에서 썼던 거랑 똑같음!

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
visited[x][y] = true;

꺼내면서 네 방향 체크
조건 맞으면 줄에 넣고 방문 처리. 

 

---

 

6. 암기하는 나만의 공식

 

6.1 첫번째 문제

1. 방향 배열 먼저 만들기
2. 줄과 방문 배열 만들기
3. 시작점 큐에 넣고 방문 표시
4. 줄 빌 때까지 반복:
  - 하나 꺼내서 현재 위치 확인
  - 도착점이면 true 반환
 - 네 방향 확인 : 갈 수 있으면 큐에 넣고 방문 처리
5. 도착 못 했으면 false

 

6.2 두번째 문제

1. maxHeight까지 height 하나씩 돌려
2. visited 배열은 높이마다 새로 만들고
3. 모든 칸을 돌며, 안 잠겼고, 방문 안했으면 BFS 시작! , safeZone++
4. BFS는 네 방향 돌며, 범위 안, 방문 안 했고, height보다 높은 곳이면 줄에 추가
5. height별 safeZone 최댓값 출력

 

 

---

 

7.  이 문제에서 배운 논리를 다른 문제에 활용할 수 있는 BFS 문제 패턴

문제	핵심개념
섬의 개수 (백준 4963) https://www.acmicpc.net/problem/4963	연결된 덩어리 개수 세기 (물 대신 바다)
단지 번호 붙이기 (백준 2667) https://www.acmicpc.net/problem/2667	1로 연결된 집 그룹 세기
미로 탐색 (2178) https://www.acmicpc.net/problem/2178	최단거리 탐색
유기농 배추 (1012) https://www.acmicpc.net/problem/1012	배추 뭉치 개수 (DFS/BFS)
바이러스 퍼지기	감염 시뮬레이션 (큐, visited, 조건)