[JAVA] 백준 1987 - 알파벳

 

 

dfs + 백트래킹을 구현만 하면 정답인 문제였고

HashSet의 add(), remove(), contains()가 O(1)인것을 이용해 HashSet을 통해 풀었다.

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.util.HashSet;


    public class Main {

        public static int max = Integer.MIN_VALUE;
        public static int R ;
        public static int C ;
        public static String[][] map;
        public static HashSet<String> set = new HashSet<>();
        public static void main(String[] args) throws Exception {

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] line = br.readLine().split(" ");
            R = Integer.parseInt(line[0]);
            C = Integer.parseInt(line[1]);
            map = new String[R][C];
            for(int i = 0 ; i < R ; i++){
                line = br.readLine().split("");
                for(int j = 0 ; j < C ; j++){
                    map[i][j] = line[j];
                }
            }

            dfs(0,0, 1 );
            System.out.println(max);


        }

        public static void dfs(int x, int y , int step){
            if(set.contains(map[x][y])) return;
            max = Integer.max(step, max);
            set.add(map[x][y]);

            if(x - 1 >= 0 && !set.contains(map[x -1][y])){ // 상
                dfs(x - 1, y , step + 1 );
            }
            if(x + 1 < R && !set.contains(map[x + 1][y])){ // 하
                dfs(x + 1, y , step + 1 );
            }

            if(y - 1 >= 0 && !set.contains(map[x][y - 1])){ // 좌
                dfs(x , y - 1 , step + 1 );
            }

            if(y + 1 < C && !set.contains(map[x][y+ 1])){ // 우
                dfs(x, y + 1 , step + 1 );
            }

            set.remove(map[x][y]);
        }


    }