백준 14529: Where's Bessie? (Java)

접근

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

14529번: Where's Bessie?

문제 해석: 농부 존이 카메라가 장착된 드론으로 자신의 소를 찾으려고 합니다. 이미지에서 소를 찾을 수 있는 알고리즘을 고안해야 하는데, 이때 소가 있을 만한 위치가 PCL이다. PCL의 조건은 두가지입니다. 첫번째로 두가지의 알파벳으로만 이루어져야 한다는 것입니다. 둘째로 앞의 두가지의 알파벳 중 하나는 해당 PCL 내에서 모두 연결되어 있어야 하며, 나머지 하나의 알파벳은 두개 이상의 그룹으로 나뉘어 있어야 합니다. PCL의 subgrid는 탐색할 필요 없다고 되어있기 때문에, 큰 크기의 탐색 범위가 PCL로 지정되면 그 내부에 속한 모든 점은 PCL로 간주합니다.

크기가 w, h 인 상자가 PCL 인지 탐색하기 위해서 해당 상자가 몇개의 알파벳으로 이루어져 있는지 확인하고, 또 각각의 알파벳이 몇개의 그룹으로 나누어져 있는지를 탐색해주게 됩니다. 탐색 후 PCL의 조건에 해당한다면 해당 상자의 내부를 모두 PCL에 해당한다고 저장해주면서 탐색을 계속합니다.

PCL의 subgrid의 중복 탐색을 막기 위해, 크기가 큰 상자에서 부터 점점 크기를 줄여가면서 탐색을 진행해주었습니다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

  static int N, ans;
  static char[][] map;
  static boolean[][][][] mark;
  static int[] dr = { 0, 1, 0, -1 };
  static int[] dc = { 1, 0, -1, 0 };

  static class Node {

    private int r, c;

    public Node(int r, int c) {
      this.r = r;
      this.c = c;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    map = new char[N][N];
    mark = new boolean[N][N][N][N];
    for (int i = 0; i < N; i++) {
      String tmp = br.readLine();
      for (int j = 0; j < N; j++) {
        map[i][j] = tmp.charAt(j);
      }
    }
    br.close();
    for (int h = N - 1; 0 <= h; h--) {
      for (int w = N - 1; 0 <= w; w--) {
        // 크기가 w, h 인 상자 탐색
        for (int r = 0; r + h < N; r++) {
          for (int c = 0; c + w < N; c++) {
            // 탐색 중인 크기가 w, h 인 상자가 PCL인지 아닌지 확인
            if (mark[r][c][r + h][c + w]) continue;
            Node from = new Node(r, c);
            Node to = new Node(r + h, c + w);
            if (isPCL(from, to)) {
              marking(from, to);
              ans++;
            }
          }
        }
      }
    }
    System.out.println(ans);
  }

  static boolean isPCL(Node from, Node to) {
    boolean[][] visited = new boolean[N][N];
    int[] visited_color = new int[27];
    int color_num = 0;
    for (int r = from.r; r <= to.r; r++) {
      for (int c = from.c; c <= to.c; c++) {
        if (visited[r][c]) continue;
        char now_color = map[r][c];
        if (visited_color[now_color - 'A'] == 0) color_num++;
        // 현재 탐색중인 상자에 알파벳의 종류가 3종 이상일 경우 PCL 이 아니므로 탐색 종료
        if (color_num > 2) return false;
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(new Node(r, c));
        while (!queue.isEmpty()) {
          Node now = queue.poll();
          for (int i = 0; i < 4; i++) {
            int nr = now.r + dr[i];
            int nc = now.c + dc[i];
            if (nr < from.r || to.r < nr || nc < from.c || to.c < nc || visited[nr][nc] || map[nr][nc] != now_color) continue;
            visited[nr][nc] = true;
            queue.add(new Node(nr, nc));
          }
        }
        visited_color[now_color - 'A']++;
      }
    }
    int color1 = 0;
    int color2 = 0;
    for (int i = 0; i < 26; i++) {
      if (visited_color[i] == 0) continue;
      if (visited_color[i] == 1) {
        color1 = visited_color[i];
      } else {
        color2 = visited_color[i];
      }
    }
    // PCL의 조건에 부합할 경우 true 리턴
    if (color1 == 1 && color2 >= 2) return true;
    return false;
  }

  // PCL 이라고 탐색된 상자의 내부를 모두 PCL로 마킹해주는 함수
  static void marking(Node from, Node to) {
    for (int r = from.r; r <= to.r; r++) {
      for (int c = from.c; c <= to.c; c++) {
        for (int i = r; i <= to.r; i++) {
          for (int j = c; j <= to.c; j++) {
            mark[r][c][i][j] = true;
          }
        }
      }
    }
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!