[DFS] 백준 - 1987번: 알파벳 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

1987번: 알파벳

 

문제는 알파벳으로 된 맵이 있는데 말이 0, 0부터 시작하여 중복되지 않는 알파벳만 이동할 수 있다.

예제 1번을 그림으로 표현한다면

 

첫 번째 경우의 수로 말은 C - A - D 순으로 방문할 수 있고,

 

두 번째 경우의 수는 위와 같이 순서는 똑같지만 가는 방향이 다르다.

 

따라서 dfs를 호출할 때는 먼저 main에서 한 번만 호출하는데 이때는 무조건 0, 0부터 시작할 것이다.

 

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static char[][] map;
    static List<Character> checkedAlphabet;
    static int r;
    static int c;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        r = sc.nextInt();
        c = sc.nextInt();
        sc.nextLine();

        map = new char[r][c];
        checkedAlphabet = new ArrayList<>();

        for (int i = 0; i < r; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = s.charAt(j);
            }
        }

        max = 0;
        dfs(0, 0, 0);

        System.out.println(max);
    }


    private static void dfs(int x, int y, int count) {
        if (checkedAlphabet.contains(map[x][y])) {
            max = Math.max(max, count);
            return;
        }

        checkedAlphabet.add(map[x][y]);

        for (int i = 0; i < 4; i++) {
            int nowX = x + dx[i];
            int nowY = y + dy[i];

            if (nowX >= 0 && nowY >= 0 && nowX < r && nowY < c) {
                dfs(nowX, nowY, count + 1);
            }
        }

        checkedAlphabet.remove(Character.valueOf(map[x][y]));
    }
}

 

나 같은 경우에는 방문한 곳을 List로 구성하여 contains로 방문했는지 확인하고 방문했다면 max 값을 경신해주고, 방문 안 해줬다면 다시 dfs를 돌려서 카운트를 1을 올려주었다.

그래서 dfs는 이렇게 짜주면 되는데 

 

마지막에 여러 경우의 수를 위하여 첫 시작 지점 제외하고 요소를 삭제해줘야 하는데 

요소를 삭제 안 하고 계속 삽질하고 있었다...허허