[SHISENSHO] Shisen-sho

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

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

algospot.com :: SHISENSHO

 

풀이입니다. 🤔

 

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;
    }
}

 

이 문제는 이동할 수 있는 경로를 완전탐색하는 것으로 문제를 해결해볼 수 있습니다.

 

- 경로를 변경할 수 있는 횟수는 최대 3회입니다. (첫 번째 방향 선택도 경로를 선택한 것으로 봅니다.)
- 경로 탐색 중 주어진 W,H 를 넘을 수 없습니다. 
- 경로 탐색 중 빈 칸(.) 이 아닌 문자가 나온다면, 탐색을 멈춥니다. (같은 문자라면, 해당 좌표를 기억해야 합니다.)

 

 

완전 탐색을 거친 후 중복된 집합을 제거하기 위해, index 가 빠른 순을 기준으로 횟수를 기록하도록 합니다.

위의 두 과정을 거치게 되면, 문제를 해결해 볼 수 있습니다. 

 

 

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