평가

1회 실패 후 성공

풀이시간

1회 : 32분
2회 : +3분

실패원인

종료조건 누락

흐름

문제의 흐름은 다음과 같습니다.
1. (0,0) 에서 이동한다
2. 이동한 지점의 알파벳을 확인한다
3. 이미 방문한 알파벳이라면 종료한다.
4. 방문하지 않은 알파벳이라면 다음 경로를 확인한다.
5. 가장 긴 경로를 찾는다.

첫 번째 풀이(성공/시간 오래 걸림)

기본적으로 dfs를 사용하는 문제입니다. 현재 위치에서 이동가능한 지점들로 이동합니다.
이동한 위치의 알파벳이 이미 사전에 나온 알파벳인지 확인하는 로직이 필요한데,
해당 풀이에서는 HashSet을 사용해 경로들을 기록해줬습니다.
만약 HashSet의 contains 메서드가 true가 된다면 해당 알파벳은 사전에 나온 알파벳이기 때문에 해당 케이스는 불가능한 케이스가 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static int answer = 0;
    static int[] dx = new int[] {1, 0, -1, 0};
    static int[] dy = new int[] {0, 1, 0, -1};
    static int R, C;
    static char[][] graph;
    static boolean[][] visited;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        graph = new char[R][C];
        visited = new boolean[R][C];
        for (int i = 0; i < R; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                graph[i][j] = temp[j];
            }
        }


        // 첫 방문처리
        visited[0][0] = true;
        Set<Character> routes = new HashSet<>();
        routes.add(graph[0][0]);
        dfs(new Node(0, 0), routes);

        System.out.println(answer);
    }

    public static void dfs(Node now, Set<Character> routes) {
        for (int d = 0; d < 4; d++) {
            int nx = now.x + dx[d];
            int ny = now.y + dy[d];
            if (nx < 0 || ny < 0 || R <= nx || C <= ny) {
                answer = Math.max(answer, routes.size());
                continue;
            }
            if (visited[nx][ny]) {
                answer = Math.max(answer, routes.size());
                continue;
            }

            // 같은 문자열이 나와서 해당 방향으로 더 진행 불가능
            if (routes.contains(graph[nx][ny])) {
                answer = Math.max(answer, routes.size());
                continue;
            }

            Node next = new Node(nx, ny);
            routes.add(graph[nx][ny]);
            visited[nx][ny] = true;
            dfs(next, routes);
            routes.remove(graph[nx][ny]);
            visited[nx][ny] = false;
        }
    }

    public static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }
}

개선된 풀이

위의 풀이에서는 HashSet을 사용해 알파벳이 사전에 나왔는지 검사한다고 말씀드렸습니다. 하지만 알파벳은 26자리의 제한된 경우들이 존재합니다. 따라서 배열을 사용해 사전에 나왔는지를 확인할 수 있습니다.

변경된 로직은 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int answer = 0;
    static int[] dx = new int[] {1, 0, -1, 0};
    static int[] dy = new int[] {0, 1, 0, -1};
    static int R, C;
    static char[][] graph;
    static boolean[] alpha = new boolean[26]; // 알파벳 26개 맞나?


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        graph = new char[R][C];
        for (int i = 0; i < R; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                graph[i][j] = temp[j];
            }
        }


        // 첫 방문처리
        alpha[graph[0][0] - 'A'] = true;
        dfs(new Node(0, 0), 1);

        System.out.println(answer);
    }

    public static void dfs(Node now, int cnt) {
        for (int d = 0; d < 4; d++) {
            int nx = now.x + dx[d];
            int ny = now.y + dy[d];
            if (nx < 0 || ny < 0 || R <= nx || C <= ny) {
                continue;
            }

            // 같은 문자열이 나와서 해당 방향으로 더 진행 불가능
            if (alpha[graph[nx][ny] - 'A']) {
                continue;
            }

            Node next = new Node(nx, ny);
            alpha[graph[nx][ny] - 'A'] = true;
            dfs(next, cnt + 1);
            alpha[graph[nx][ny] - 'A'] = false;
        }
        answer = Math.max(answer, cnt);
        return;
    }

    public static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }
}