[SHISENSHO] Shisen-sho
Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.
문제 : https://www.algospot.com/judge/problem/read/SHISENSHO
algospot.com :: SHISENSHO
Shisen-sho 문제 정보 문제 Shisen-sho(in Korean, Sa-Cheon-Sung 사천성) is a board game that originated in Japan, which is popular in Korea as well. The game is played on a rectangular game board with N \times M cells, and various tiles are placed o
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
|
import java.util.*;
public class Main {
private static final char EMPTY = '.';
private static final int[][] directions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private static final char[][] boards = new char[50][50];
private static final boolean[][] foundCoordinates = new boolean[50][50];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int cases = scanner.nextInt();
while (cases-- > 0) {
int h = scanner.nextInt(), w = scanner.nextInt();
for (int i = 0; i < h; ++i) {
char[] line = scanner.next().toCharArray();
for (int j = 0, len = line.length; j < len; ++j) {
boards[i][j] = line[j];
}
}
System.out.println(getCount(h, w));
}
}
private static int getCount(int h, int w) {
int ret = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (boards[i][j] == EMPTY) continue;
for (int k = 0, len = directions.length; k < len; ++k) {
find(h, w, i + directions[k][0], j + directions[k][1], boards[i][j], k, 0);
}
ret += getCount(h, w, i, j);
}
}
return ret;
}
private static void find(int h, int w, int y, int x, char character, int direction, int turnCount) {
if (turnCount == 3) return; // 기저사례 1: 경로를 3회 초과로 변경할 수 없다.
if (y < 0 || y >= h || x < 0 || x >= w) return; // 기저 사례 2: 좌표가 주어진 영역을 벗어났다.
if (boards[y][x] == character) {
foundCoordinates[y][x] = true;
return;
} // 기저사례 3: character 와 동일한 문자를 발견
if (boards[y][x] != EMPTY) return; // 기저사례 4: character 와 동일하지 않고, 빈 문자열이 아닌 문자를 발견
for (int i = 0, len = directions.length; i < len; ++i) {
find(h, w, y + directions[i][0], x + directions[i][1], character, i, (direction == i) ? turnCount : turnCount + 1);
}
}
private static int getCount(int h, int w, int y, int x) {
int ret = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (foundCoordinates[i][j]) {
foundCoordinates[i][j] = false;
if (y > i || (y == i && x > j)) ++ret; // 중복된 경우를 제거하기 위해, 자신보다 앞에 있는 좌표는 추가하지 않음.
}
}
}
return ret;
}
}
|
cs |
이 문제는 이동할 수 있는 경로를 완전탐색하는 것으로 문제를 해결해볼 수 있습니다.
- 경로를 변경할 수 있는 횟수는 최대 3회입니다. (첫 번째 방향 선택도 경로를 선택한 것으로 봅니다.)
- 경로 탐색 중 주어진 W,H 를 넘을 수 없습니다.
- 경로 탐색 중 빈 칸(.) 이 아닌 문자가 나온다면, 탐색을 멈춥니다. (같은 문자라면, 해당 좌표를 기억해야 합니다.)
완전 탐색을 거친 후 중복된 집합을 제거하기 위해, index 가 빠른 순을 기준으로 횟수를 기록하도록 합니다.
위의 두 과정을 거치게 되면, 문제를 해결해 볼 수 있습니다.
이 포스트를 읽어주셔서 감사합니다. 🙇🏻♂️
'개발이야기 > 알고스팟' 카테고리의 다른 글
| [FIXPAREN] Mismatched Parenthesis (0) | 2022.01.04 |
|---|---|
| [BRACKETS2] Mismatched Brackets (0) | 2022.01.03 |
| [WEEKLYCALENDAR] Weekly Calendar (0) | 2022.01.03 |
| [CLOCKSYNC] Synchronizing Clocks (0) | 2022.01.02 |
| [HAMMINGCODE] Hamming Code (0) | 2021.12.30 |