[CCR] 문자 인식
개발이야기/알고스팟2022. 1. 9. 17:37
Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.
문제 : https://www.algospot.com/judge/problem/read/CCR
algospot.com :: CCR
문자 인식 문제 정보 문제 DCinside에 알고리즘 갤러리가 생겼다! 그러나 알고리즘 갤러리는 수많은 수갤러스(수능 갤러리 유저)들의 공격을 받곤 했는데, 수학 I 교과목에서 가장 쉬운 부분이 알
www.algospot.com
풀이입니다. 🤔
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
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;
}
}
|
cs |
문제의 내용 중 주의할 내용은 아래와 같습니다.
문자들은 바로 옆에 인접하지 않으므로 연속된 검은 색 격자칸들의 집합이 어떠한 문자도 표현하지 않는 잘못된 경우는 존재하지 않는다.
숫자를 인식하기 위해 모든 특징에 맞춰 격자칸들의 집합을 순회하는 것이 아닌, 문자에 존재하는 특이점을 이용해서 인식하도록 한다면 쉽게 문제를 해결해볼 수 있습니다.
특이점의 예시는 다음과 같습니다.
- 1 과 4 의 경우는 시작점의 오른쪽에는 격자가 존재하지 않습니다.
- 2, 3 그리고 7은 시작점의 오른쪽에는 격자가 존재하지만 아래쪽에는 존재하지 않습니다.
- 5 와 6 의 시작점으로 오른쪽 끝 격자로부터 아래칸은 존재하지 않습니다.
- ....
이 포스트를 읽어주셔서 감사합니다. 🙇🏻♂️
반응형
'개발이야기 > 알고스팟' 카테고리의 다른 글
| [QUADTREE] 쿼드 트리 뒤집기 (0) | 2022.01.14 |
|---|---|
| [JOSEPHUS] 조세푸스 문제 (0) | 2022.01.09 |
| [SPETIAL] Spatial Concepts Test (0) | 2022.01.09 |
| [WORDLENGTH] 단어 길이 재기 (0) | 2022.01.07 |
| [MVP] Most Valuable Programmer (0) | 2022.01.07 |