[자바] 백준 26598 - 색종이와 공예 (java)

목차

문제 : boj26598

 

 

필요 알고리즘

• 애드 혹(ad hoc), 그래프 탐색(dfs, bfs)
  
  • 이 문제만의 규칙을 찾아 해결하는 애드혹 문제이다. 구현을 위해 그래프 탐색을 사용했다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  내 경우 이하의 로직으로 진행했다.

1. 맵의 좌측상단부터 우측 하단으로 진행하면서, 이미 찾은 직사각형임을 찾은 곳은 체크를 해둔다 (다시 직사각형의 여부를 확인하지 않아도 되도록).

 

 

2. 아직 방문하지 않은 곳을 만났다면, 해당 지점부터 동일한 문자를 만날 때 까지 우측으로 진행하며 해당 직사각형의 너비를 계산한다. 그리고 동일한 문자를 만날 때 까지 아래로 진행하며 해당 직사각형의 높이를 계산한다. 예를들어 처음 A를 만났다면, 우측으로 가보니 A는 2칸이고 아래로 가보니 A는 3칸이었다. 따라서 해당 지점부터 2x3 지점을 모두 살펴보는 것이다. (코드의 findRange())

 

 

 

3. 이 때 탐색 시 만약 해당 사이즈에서 다른 문자를 만나거나, 상하좌우로 한칸 씩 더 살펴보아 만약 동일한 문자가 있다면 직사각형이 아닌 경우이다. (코드의 possible())

 

4. 위의 과정을 반복한다.

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    int r, c;
    char[][] arr;
    boolean[][] v;

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        arr = new char[r][c];
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                arr[i][j] = row.charAt(j);
            }
        }

        v = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (v[i][j]) continue;

                int[] range = findRange(i, j);
                if (!possible(i, j, range[0], range[1])) {
                    System.out.println("BaboBabo");
                    return;
                }
            }
        }

        System.out.println("dd");
    }

    private boolean possible(final int rs, final int cs, final int re, final int ce) {
        char target = arr[rs][cs];
        for (int i = rs; i <= re; i++) {
            for (int j = cs; j <= ce; j++) {

                v[i][j] = true;
                if (arr[i][j] != target)
                    return false;

                if (i == rs && i-1 >= 0 && arr[i-1][j] == target)
                    return false;

                if (i == re && i+1 < r && arr[i+1][j] == target)
                    return false;

                if (j == cs && j-1 >= 0 && arr[i][j-1] == target)
                    return false;

                if (j == ce && j+1 < c && arr[i][j+1] == target)
                    return false;

            }
        }

        return true;
    }

    private int[] findRange(final int y, final int x) {
        char target = arr[y][x];

        int i = y;
        while (i < r && arr[i][x] == target) i++;
        int j = x;
        while (j < c && arr[y][j] == target) j++;

        return new int[]{i-1, j-1};
    }
}