[SWEA] 7699. 수지의 수지 맞는 여행 (D4) (Java)

[SWEA] 7699. 수지의 수지 맞는 여행 (D4) (Java)

Problem

제출일 : 2020-02-18

문제 풀이 시간 : 15M

난이도 : ★

---

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqUzj0arpkDFARG

평소에 여행을 즐기는 수지는 이번에 새로운 섬에 도착했다.

이 섬은 1행, 1열로 시작해서 R행, C열까지 있으며, 총 R*C 칸으로 이루어져 있다.

수지는 지금 1행 1열에 있으며 앞으로 있을 야근을 위하여 기회 있을 때 미리 여행을 떠나려고 한다.

이 섬의 각 칸에는 알파벳이 적혀있다. 이 알파벳은 섬의 명물이고, 같은 알파벳은 같은 명물이다.

이 섬에서는 명물을 볼 때마다 요금을 지급해야 하는데 각 알파벳 명물을 처음 볼 땐 무료로 볼 수 있다.

그리고, 수지는 여행을 할 때 자신이 있는 지점의 명물을 본 후 4방향(상, 하, 좌, 우) 중 한 방향으로 1칸 이동 후 다음 명물을 보는 행동을 반복한다.

올해 SGA사 1년 차인 수지는 현재 대출빚과 카드빚에 허덕이고 있다.

따라서, 명물을 최대한 많이 보되, 요금을 지급하지 않는 방법을 택해야 한다.

수지가 1행 1열에서 여행을 시작했을 때, 같은 알파벳 명물을 두 번 이상 보지 않도록 여행을 떠나는 방법 중에 볼 수 있는 명물의 최대 개수를 구하여라.

input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 섬의 크기 R,C(1≤R,C≤20)가 주어진다.

이어서 R개의 줄마다 C개의 알파벳 대문자가 빈 칸 없이 주어진다.

Output

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

각 테스트 케이스마다 수지가 여행하면서 볼 수 있는 명물 개수의 최대치를 출력하라.

Example

input

3
2 4
CAAB
ADCB
3 6
HFDFFB
AJHGDH
DGAGEH
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

output

#1 3
#2 6
#3 10

Solution & Inpression

알파벳이 같으면 요금을 지불해야 되기때문에 가지 않았다. 따라서 방문 처리를 알파벳의 개수의 배열을 이용하여 방문처리를 하였고 항상 최대값을 갱신해주었다.

Code

언어 : JAVA

메모리 : 24,648 kb

실행시간 : 2,068 ms

import java.util.Scanner;

class Solution {
    static int T, R, C, ans;
    static char[][] map;
    static boolean[] visit;

    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            R = sc.nextInt();
            C = sc.nextInt();
            map = new char[R][C];
            for (int i = 0; i < R; i++) {
                String str = sc.next();
                for (int j = 0; j < C; j++) {
                    map[i][j] = str.charAt(j);
                }
            }
            ans = 0;
            visit = new boolean[26];
            visit[map[0][0] - 'A'] = true;
            DFS(0, 0, 1);
            System.out.println("#" + tc + " " + ans);
        } // end of TC
    }

    private static void DFS(int i, int j, int depth) {
        if (depth > ans)
            ans = depth;
        for (int dir = 0; dir < dc.length; dir++) {
            int r = i + dr[dir];
            int c = j + dc[dir];
            if (isRange(r, c) && !visit[map[r][c] - 'A']) {
                visit[map[r][c] - 'A'] = true;
                DFS(r, c, depth + 1);
                visit[map[r][c] - 'A'] = false;
            }

        }
    }

    private static boolean isRange(int r, int c) {
        if (0 <= r && r < R && 0 <= c && c < C)
            return true;
        return false;
    }
}