[BOJ] 1987번 : 알파벳

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

 

 

분류 : DFS, 백트래킹

 

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static final int inf = 987654321;
    static char[][] alpha;

    static int N, M, ml = 0;

    public static void main(String[] args) {
        N = sc.nextInt();
        M = sc.nextInt();
        alpha = new char[N][M];
        for (int r = 0; r < N; r++) {
            alpha[r] = sc.nextLine().toCharArray();
        }
        DFS(0, 0, "");
        out.println(ml);
        out.close();
    }

    private static void DFS(int r, int c, String str) {
        
        if(ml<str.length()){
            ml = str.length();
        }
        if (r < 0 || r >= N || c < 0 || c >= M  || str.contains(alpha[r][c]+""))
            return;
        
        str += alpha[r][c];
        DFS(r + 1, c, str);
        DFS(r - 1, c, str);
        DFS(r, c + 1, str);
        DFS(r, c - 1, str);
    }
}

 

처음에 visited 배열과 str을 둘 다 쓰니 제출하자마자 바로 틀렸다..ㅠ.ㅠ

뭐가 문제지 하고서 디버깅을 하며 출력해보니까 DFS를 돌면서 이상한 값이 나오기에 visited 배열은 제거하고 String 만을 이용해서 DFS를 구현하니 통과 완료..

하지만 제일 빠른 코드와 내 코드의 시간 격차가 어마어마 하더라..

 

제일 빠른 분은 132ms로 거의 10배가 차이가 난다.

그분의 코드를 참조하여 좀 더 최적화하는 연습을 해야겠다.