[백준 1987] 알파벳(Java)

[백준 1987] 알파벳(Java)

1987번: 알파벳

1987번: 알파벳

 

해결 방법

1트

DFS를 사용하여 모든 경로를 탐색하고 경로의 길이가 가장 긴 것을 출력하면 되는 문제 입니다.

풀이

public class Quiz1987 {

    static int r;
    static int c;
    // 상, 하, 좌, 우
    static int[] ud = {1, -1, 0, 0};
    static int[] lr = {0, 0, 1, -1};
    static Character[][] map;
    static boolean[][] visited;
    // 알파벳은 총 26개
    static Character[] path = new Character[26];
    static int max = Integer.MIN_VALUE;

    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());

        // 같은 알파벳을 지날 수 없다.
        // 시작점은 0, 0에서 최대 몇 칸을 움직 일 수 있는지 구하시오.


        // 알파벳 저장
        map = new Character[r][c];
        for(int i = 0; i < r; i++) {
            String str = br.readLine();
            char[] chars = str.toCharArray();
            for(int j = 0; j < c; j++) {
                map[i][j] = chars[j];
            }
        }

        // 시작점 
        visited = new boolean[r][c];
        visited[0][0] = true;
        path[0] = map[0][0];
         // dfs 수행
        dfs(0, 0, 0, String.valueOf(map[0][0]));

        System.out.print(max);
        br.close();
    }

    private static void dfs(int x, int y, int depth, String path) {

        max = Math.max(path.length(), max);

        for(int i = 0; i < 4; i++) {
            int newX = x + ud[i];
            int newY = y + lr[i];

            // 범위 체크
            if(newX < 0 || newY < 0 || newX >= r || newY >= c) {
                continue;
            }

            // 방문 이력없고 지나온 알파벳이 없으면
            if(!visited[newX][newY] && !path.contains(String.valueOf(map[newX][newY]))) {
                visited[newX][newY] = true;
                dfs(newX, newY, depth + 1, path + map[newX][newY]);
                visited[newX][newY] = false;
            }
        }
    }
}

 

그런데….

 

메모리와 시간이 너무 안좋습니다..

해결 방법2

메모리와 시간을 어떻게 줄이지…?🤔
제 생각으로는 path에 계속해서 String을 생성해서 메모리와 시간에서 효율이 안 좋다고 판단했습니다.

제 머리로는 path를 없애는 방법이 떠오르지 않아서
다른 사람의 풀이를 참고 했습니다..

 

방법은 바로 바로 바로

방문 이력을 알파벳 사용 했는지 안했는지로 사용하면됩니다!!

// 알파벳은 총 26개
static boolean[] path = new boolean[26];

// 알파벳 저장
map = new Character[r][c];

// 알파벳 사용 유무
path[map[newX][newY] - 'A'] = true;
path[map[newX][newY] - 'A'] = false;

 

이런걸 생각하는 사람은 정말로 천재 같습니다..

풀이2

public class Quiz1987 {

    static int r;
    static int c;
    // 상, 하, 좌, 우
    static int[] ud = {1, -1, 0, 0};
    static int[] lr = {0, 0, 1, -1};
    // 알파벳
    static Character[][] map;
    // 알파벳은 총 26개
    static boolean[] path = new boolean[26];
    static int max = Integer.MIN_VALUE;

    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());

        // 같은 알파벳을 지날 수 없다.
        // 시작점은 0, 0에서 최대 몇 칸을 움직 일 수 있는지 구하시오.


        // 알파벳 저장
        map = new Character[r][c];
        for(int i = 0; i < r; i++) {
            String str = br.readLine();
            char[] chars = str.toCharArray();
            for(int j = 0; j < c; j++) {
                map[i][j] = chars[j];
            }
        }

        // 시작 위치
        path[map[0][0] - 'A'] = true;
        dfs(0, 0, 1);

        // 출력
        System.out.print(max);
        br.close();
    }

    private static void dfs(int x, int y, int depth) {

        // 깊이가 최대 계산
        max = Math.max(depth, max);

        for(int i = 0; i < 4; i++) {
            // 상, 하, 좌, 우 이동
            int newX = x + ud[i];
            int newY = y + lr[i];

            // 범위 체크
            if(newX < 0 || newY < 0 || newX >= r || newY >= c) {
                continue;
            }

            // 방문 이력없고 지나온 알파벳이 없으면
            if(!path[map[newX][newY] - 'A']) {
                // 알파벳 사용
                path[map[newX][newY] - 'A'] = true;
                // dfs 수행
                dfs(newX, newY, depth + 1);
                // 알파벳 초기화
                path[map[newX][newY] - 'A'] = false;
            }
        }
    }
}

 

와 약 2,000ms정도가 빨라졌고, 메모리 사용량은 약 285,000KB 나 줄었습니다!!!