백준 알고리즘 2583번: 영역 구하기

문제 정보

---

2583번: 영역 구하기

 

 

핵심

---

그래프 탐색 알고리즘을 사용하여 문제를 풀이하자!

다만, 처음에 고민되었던 부분은 각 영역의 오른쪽 위 꼭짓점의 좌표값을 어떻게 처리하느냐.. 였는데

꼭짓점을 좌표라고 생각하지 말고, 해당 영역을 좌표라고 생각해 보는 것이 도움이 되었던 것 같다

예를 들어 (0, 0)은 왼쪽 아래 꼭짓점이라고 생각하기보다는 첫번째 (왼쪽 아래) 영역이라고 생각하면

map[0][0]은 해당 영역을 나타내는 값이 되는 것이다

 

간단하게 그림으로 나타내 보았는데, (0,0) (3, 2)가 입력되는 경우라면 해당 영역이 포함하는 구간은

(0, 0)부터 (2, 1) = (3-1, 2-1) 까지의 영역을 나타내는 것으로

그 사이의 모든 영역에 대한 처리를 해주면 쉽게 풀이할 수 있다

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

class Main {

  static boolean[][] visited;
  static int M;
  static int N;
  static int local = 0;
  static int[][] moveTo = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    M = Integer.parseInt(st.nextToken());
    N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    boolean[][] map = new boolean[M][N];
    visited = new boolean[M][N];

    for (int i = 0; i < K; i++) {
      st = new StringTokenizer(br.readLine());
      int startX = Integer.parseInt(st.nextToken());
      int startY = Integer.parseInt(st.nextToken());
      int endX = Integer.parseInt(st.nextToken());
      int endY = Integer.parseInt(st.nextToken());

      fill(startX, startY, endX, endY, map);
    }

    List<Integer> result = new ArrayList<>();
    for (int y = 0; y < M; y++) {
      for (int x = 0; x < N; x++) {
        if (!map[y][x] && !visited[y][x]) {
          visited[y][x] = true;
          dfs(x, y, map);
          result.add(local);
          local = 0;
        }
      }
    }
    System.out.println(result.size());
    System.out.println(
        result.stream().sorted().map(String::valueOf).collect(Collectors.joining(" ")));
  }

  public static void fill(int startX, int startY, int endX, int endY, boolean[][] map) {
    for (int y = startY; y < endY; y++) {
      for (int x = startX; x < endX; x++) {
        map[y][x] = true;
      }
    }
  }

  public static void dfs(int curX, int curY, boolean[][] map) {
    local += 1;
    for (int[] move : moveTo) {
      int nextX = curX + move[0];
      int nextY = curY + move[1];

      if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) {
        continue;
      }
      if (!visited[nextY][nextX] && !map[nextY][nextX]) {
        visited[nextY][nextX] = true;
        dfs(nextX, nextY, map);
      }
    }
  }
}

 

고찰

---

 

2667번: 단지번호붙이기

 

백준 알고리즘 2667번: 단지번호붙이기

해당 두 문제가 비슷한 문제라고 생각하여, 가져와 보았다

그래프 탐색에 대한 문제는 다들 꽤나 비슷한 부분이 많이 있기 때문에 여러 문제를 풀어보는 것을 추천한다!

 

 

Source Code on GitHub

---