[ 백준 - 2468 ] 안전 영역

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

2468번: 안전 영역

물 수위에 따라서 수면에 잠기지 않은 붙어있는 영역을 구하는 문제로 간략하게 설명할 수 있을거 같다.

그래프 탐색 알고리즘을 사용해서 문제를 접근했다.

 

---

[ 📌 고려사항 ]

• N은 2 이상 100 이하 -> 지역의 총 크기는 100 * 100이 최대 사이즈다.
• H(높이)는 1이상 100 이하 -> 최대 101번의 높이에 대해서 실행해야 한다.

---

[ 📌 풀이 ]

1. 입력받은 영역들 중에가 가장 높은 지대의 높이를 기록한다.

2. 0 부터 (1)에서 입력받은 값 까지 수위를 1씩 올려가며 그래프 탐색을 하며 안전 영역을 카운팅 한다.

3. 안전 영역이 가장 많을 때로 갱신한다.

---

[ 📌 코드 - Python ]

import sys
from collections import deque
inp = sys.stdin.readline

N = int(inp())
moves = [0, 1, 0, -1]
maps = [list(map(int, inp().split())) for _ in range(N)]
max_height = max(max(row) for row in maps)
max_area = 0

def bfs(height) -> int:
  visited = [[False] * N for _ in range(N)]
  queue = deque()
  cnt = 0

  for i in range(N):
    for j in range(N):
      if maps[i][j] <= height or visited[i][j]:
        continue

      queue.append((i, j))

      while queue:
        x, y = queue.pop()
        
        for idx in range(4):
          nx = x + moves[idx]
          ny = y + moves[idx - 1]

          if isValid(nx, ny) and not visited[nx][ny] and maps[nx][ny] > height:
            queue.append((nx, ny))
            visited[nx][ny] = True
      
      cnt += 1
  
  return cnt

def isValid(x, y):
  return 0 <= x < N and 0 <= y < N

for height in range(max_height):
  max_area = max(max_area, bfs(height))

print(max_area)

[ 📌 코드 - Java  ]

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

public class Q2468 {

  public static int N;
  public static int[][] maps;
  public static int[] moves = {0, 1, 0, -1, 0};
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int max_height = 0;
    int max_area = 0;
    
    N = Integer.parseInt(br.readLine());
    maps = new int[N][N];

    for(int i = 0; i < N; i++) {
      maps[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

      // 안전 영역중 가장 높은 곳
      for(int height: maps[i]) {
        max_height = Math.max(max_height, height);
      }
    }
    
    for(int i = 0; i < max_height; i++) {
      max_area = Math.max(max_area, bfs(i));
    }

    System.out.println(max_area);
  }

  public static int bfs(int height) {
    boolean[][] visited = new boolean[N][N];
    Queue<Point> queue = new LinkedList<>();
    int cnt = 0;

    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        if(maps[i][j] <= height || visited[i][j]) {
          continue;
        }

        queue.add(new Point(i, j));

        while(!queue.isEmpty()) {
          Point curP = queue.poll();
          
          for(int k = 1; k < 5; k++) {
            int nx = curP.x + moves[k];
            int ny = curP.y + moves[k - 1];

            if(isValid(nx, ny) && !visited[nx][ny] && maps[nx][ny] > height) {
              visited[nx][ny] = true;
              queue.add(new Point(nx, ny));
            }
          }
        }
        cnt++;
      }
    }

    return cnt;
  }

  public static boolean isValid(int x, int y){
    return 0 <= x && x < N && 0 <= y && y < N;
  }
}

class Point {
  int x;
  int y;
  
  Point(int x, int y) {
    this.x = x;
    this.y = y;
  }
}

---

[ 📌 결과 - Python & Java  ]

[ Result - Java & Python ]