[백준1987] 알파벳

 이 문제는 DFS와 Backtracking을 이용해 중복되지 않은 알파벳은 방문하지 않는 조건으로 (0, 0) 에서 갈 수 있는 경로의 최대거리를 구하는 문제입니다. 저는 char 자료형 특징을 이용할 생각을 못하고 지금까지 지나온 알파벳을 ArrayList에 저장해 다음 경로로 갈 때마다 체크해주는 코드로 짜봤는데요. 시간이 8000ms가 넘길래 너무 놀라서 검색해봤는데 char 자료형을 이용하면 훨씬 수월하게 탐색할 수 있는 방법이 있었습니다. 아래에 비효율적으로 짠 코드와 최적화한 코드를 차례로 첨부하겠습니다.

 우선 대문자 알파벳이기 때문에 'A' ~ 'Z' 까지가 범위가 되며 int형으로 바꾸면 65 ~ 90이 됩니다. 그래서 저는 check 배열의 인덱스를 (입력 알파벳 - 'A' ) 이라 생각하고 지나갔는지 안지나갔는지를 저장하기로 했습니다. 예를 들어 예제를 보면, 말이 (0, 0)에서 시작하고 그 문자는 'A' 입니다. 따라서 'A' - 'A' = 0 인덱스의 값에 true를 저장하는 것입니다. 그 이후 경로를 탐색할 때 경로의 알파벳이 'A'라면 check[0] 의 값이 true 이기 때문에 더 이상 진행하지 못하게 됩니다.

 또한 visited 배열을 이용해 backtracking을 수행합니다. 백트랙킹을 이용해야 해당 경로의 탐색을 멈춘 후 한 단계 전으로 갔을 때 visited 배열의 값이 원상복귀되기 때문입니다. 이런식으로 경로의 최대값을 구한 후 반환해주는 형식입니다. 

풀이를 바꾸었더니 위의 첨부 이미지와 같이 메모리 사용과 수행 시간 모두 확연히 줄었습니다. 잘못된 알고리즘을 이용해 코드를 작성하면 초래되는 결과를 다시 한번 느끼게 된 계기가 되었습니다. 아래 첨부한 코드 중 첫번째는 char를 이용하지 않은 풀이이며, 두번째가 올바른 풀이입니다.

1. String과 ArrayList를 이용한 코드

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

public class Main {
    static int R, C;
    static String[][] alpha;
    static boolean[][] visited;
    static ArrayList<String> list = new ArrayList<>();
    static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        R = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);
        alpha = new String[R][C];
        visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            alpha[i] = br.readLine().split("");
        }

        visited[0][0] = true;
        list.add(alpha[0][0]);
        System.out.print(dfs(0, 0));
    }

    private static int dfs (int x, int y) {
        int cnt = 0;
        for (int i = 0 ; i < 4; i++) {
            int sx = x + dx[i], sy = y + dy[i];
            if (sx >= 0 && sx < R && sy >= 0 && sy < C && !visited[sx][sy]) {
                if (!check(alpha[sx][sy])) {
                    visited[sx][sy] = true;
                    list.add(alpha[sx][sy]);
                    cnt = Math.max(cnt, dfs(sx, sy));
                    visited[sx][sy] = false;
                }
            }
        }

        list.remove(list.size() - 1);
        return cnt + 1;
    }

    private static boolean check (String str) {
        for (String s : list) {
            if (s.equals(str)) return true;
        }
        return false;
    }
}

2. char를 이용한 코드