[Java] 백준 1987번 : 알파벳

문제소개

 

---

Solution1

첫 번째 풀이는 지나온 알파벳을 담는 HashSet과 배열의 방문여부를 나타내는 visited, 두 가지를 이용해 백트래킹으로 풀이했다.

public class Main {
    static HashSet<Character> set;
    static char[][] map;
    static int R, C, max;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static boolean[][] visited;


    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());
        set = new HashSet<>();
        map = new char[R][C];
        visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = line.charAt(j);
            }
        }
        set.add(map[0][0]);
        visited[0][0] = true;
        dfs(0, 0, 0);
        System.out.println(max + 1);
    }

    static void dfs(int cnt, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextY = y + dy[i];
            int nextX = x + dx[i];
            if (nextX < 0 || nextY < 0 || nextY >= R || nextX >= C) continue;
            if (visited[nextY][nextX]) continue;
            if (set.contains(map[nextY][nextX])) continue;
            set.add(map[nextY][nextX]);
            visited[nextY][nextX] = true;
            dfs(cnt + 1, nextX, nextY);
            set.remove(map[nextY][nextX]);
            visited[nextY][nextX] = false;
        }
        if (cnt > max) {
            max = cnt;
        }
    }
}

 

---

첫 번째 풀이로 AC는 받았지만, 구성한 재귀 메소드가 마음에 들지 않았다.

종료조건을 처음에 걸어두고, 그 뒤에 for문을 여는 방식으로 고치고자 생각했고,

+ HashSet을 사용하지 않아도 풀이가 가능하다고 생각했다.

 

알파벳을 A ~ Z 까지, 각 0 ~ 25로 매핑하면 visited 배열을 알파벳을 방문했는지로 생각할 수 있다.

또한, 임의의 알파벳을 방문했다는 의미는 해당 자리또한 다시 갈 수 없으므로 자연스레 알파벳 + 배열의 자리 두 가지 모두 방문처리를 동시에 할 수 있었다.

Solution2

public class Main2 {

    static int[][] map;
    static int R, C, max;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static boolean[] visited;


    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());
        map = new int[R][C];
        visited = new boolean[26];

        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = line.charAt(j) - 'A';
            }
        }

        dfs(0, 0, 0);
        if (max == 0) {
            System.out.println(1);
        } else System.out.println(max);
    }

    static void dfs(int cnt, int x, int y) {
        if (visited[map[y][x]]) {
            if (cnt > max) {
                max = cnt;
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextY = y + dy[i];
            int nextX = x + dx[i];
            if(nextY < 0 || nextX < 0 || nextY >= R || nextX >= C) continue;
            visited[map[y][x]] = true;
            dfs(cnt + 1, nextX, nextY);
            visited[map[y][x]] = false;
        }
    }
}