[CCR] 문자 인식

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/CCR

algospot.com :: CCR

 

풀이입니다. 🤔

 

import java.util.Scanner;
 
public class Main {
    private static final char STAR = '*', BLANK = '_';
    private static final char[][] board = new char[25][81];
    private static final int[] PLACE = {0, 0}, TOP = {-1, 0}, RIGHT = {0, 1}, BOTTOM = {1, 0}, LEFT = {0, -1};
    private static final int[][] directions = new int[][]{TOP, RIGHT, BOTTOM, LEFT};
    private static int r, c;
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            r = scanner.nextInt();
            c = scanner.nextInt();
            for (int i = 0; i < r; ++i) {
                String line = scanner.next();
                for (int j = 0; j < c; ++j) board[i][j] = line.charAt(j);
            }
 
            int ret = 0;
            for (int y = 0; y < r; ++y) {
                for (int x = 0; x < c; ++x) {
                    if (board[y][x] != STAR) continue;
                    if (!hasStar(y, x, RIGHT)) ret += get14(y, x);
                    else {
                        if (hasStar(y, x, BOTTOM)) ret += get05689(y, x);
                        else ret += get237(y, x);
                    }
 
                    clearStar(y, x);
                }
            }
 
            System.out.println(ret);
        }
    }
 
    private static int getEndOfStarCount(int y, int x, int[] direction) {
        int ret = 0;
        for (int ny = y, nx = x; hasStar(ny, nx, direction); ny += direction[0], nx += direction[1]) {
            ++ret;
        }
        return ret;
    }
 
    private static boolean hasStar(int y, int x, int[] direction) {
        int ny = y + direction[0], nx = x + direction[1];
        return ny >= 0 && ny < r && nx >= 0 && nx < c && board[ny][nx] == STAR;
    }
 
    private static void clearStar(int y, int x) {
        board[y][x] = BLANK;
        for (int[] direction : directions) {
            int ny = y + direction[0], nx = x + direction[1];
            if (hasStar(ny, nx, PLACE)) clearStar(ny, nx);
        }
    }
 
    private static int get05689(int y, int x) {
        int endOfRightCount = getEndOfStarCount(y, x, RIGHT);
        int ny = y + RIGHT[0] * endOfRightCount, nx = x + RIGHT[1] * endOfRightCount;
        if (hasStar(ny, nx, BOTTOM)) {
            return get089(y, x, y + getEndOfStarCount(ny, nx, BOTTOM));
        } else {
            return get56(y, x);
        }
    }
 
    private static int get089(int y, int x, int endOfY) {
        int ny = y, nx = x, rightCount = 0;
        while (hasStar(ny, nx, BOTTOM)) {
            ny += BOTTOM[0]; nx += BOTTOM[1];
            if (hasStar(ny, nx, RIGHT)) ++rightCount;
        }
 
        if (ny != endOfY) return 9;
        else {
            switch (rightCount) {
                case 1: return 0;
                case 2: return 8;
                default: throw new IllegalArgumentException();
            }
        }
    }
 
    private static int get56(int y, int x) {
        int ny = y, nx = x, rightCount = 0;
        while (hasStar(ny, nx, BOTTOM)) {
            ny += BOTTOM[0]; nx += BOTTOM[1];
            if (hasStar(ny, nx, RIGHT)) ++rightCount;
        }
 
        switch (rightCount) {
            case 1: return 5;
            case 2: return 6;
            default: throw new IllegalArgumentException();
        }
    }
 
    private static int get237(int y, int x) {
        int endOfRightCount = getEndOfStarCount(y, x, RIGHT);
        int ny = y + RIGHT[0] * endOfRightCount, nx = x + RIGHT[1] * endOfRightCount, leftCount = 0;
        while (hasStar(ny, nx, BOTTOM)) {
            ny += BOTTOM[0]; nx += BOTTOM[1];
            if (hasStar(ny, nx, LEFT)) ++leftCount;
        }
 
        switch (leftCount) {
            case 0: return 7;
            case 1: return 2;
            case 2: return 3;
            default: throw new IllegalArgumentException();
        }
    }
 
    private static int get14(int y, int x) {
        int ny = y, nx = x;
        while (hasStar(ny, nx, BOTTOM)) {
            ny += BOTTOM[0]; nx += BOTTOM[1];
            if (hasStar(ny, nx, RIGHT) || hasStar(ny, nx, LEFT)) return 4;
        }
 
        return 1;
    }
}

 

문제의 내용 중 주의할 내용은 아래와 같습니다. 

 

문자들은 바로 옆에 인접하지 않으므로 연속된 검은 색 격자칸들의 집합이 어떠한 문자도 표현하지 않는 잘못된 경우는 존재하지 않는다.

 

숫자를 인식하기 위해 모든 특징에 맞춰 격자칸들의 집합을 순회하는 것이 아닌, 문자에 존재하는 특이점을 이용해서 인식하도록 한다면 쉽게 문제를 해결해볼 수 있습니다. 
특이점의 예시는 다음과 같습니다.

- 1 과 4 의 경우는 시작점의 오른쪽에는 격자가 존재하지 않습니다. 
- 2, 3 그리고 7은 시작점의 오른쪽에는 격자가 존재하지만 아래쪽에는 존재하지 않습니다.
- 5 와 6 의 시작점으로 오른쪽 끝 격자로부터 아래칸은 존재하지 않습니다.
- ....

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️