[백준 - 1987] 알파벳 - Java

문제 설명

 

1987번: 알파벳

 

풀이 회고

해당 문제는 DFS(깊이 우선 탐색)을 이용하여 풀 수 있었습니다.

 

깊이 우선 탐색을 통해 (0, 0) 지점에서 출발했을 때 탐색할 수 있는 모든 경로에 대해 탐색 종료 시의 이동한 칸 수를 검사하여 이들 중 가장 이동을 많이 한 횟수를 구하도록 했습니다. 다만, 이 문제의 경우 기존 깊이 우선 탐색이랑 다르게 접근했었던 방식이 있는데, 우선 별도의 방문 처리를 하지 않았다는 점이었습니다.

 

왜냐하면 모든 경로에 대해 검사해야하기 때문에 boolean형 2차원 배열 등 객체를 통해 방문 처리를 하다보면 어떤 깊이 우선 탐색 경로가 방문 처리를 하면서 다른 깊이 우선 탐색 경로들의 탐색에 영향을 줄 수 있기 때문입니다. 사실 애초에 탐색 종료 조건 자체가 기존 보드판의 범위를 벗어나는 경우(x < 0 || x > r - 1 || y < 0 || y > c - 1)를 포함하여 이미 밟은 알파벳을 또 밟을 경우이기 때문에 다른 방식으로 탐색을 종료해줄 필요가 있었습니다.

 

이를 위하여 당초에는 HashMap을 사용하여 알파벳을 탐색할 때마다 해당 알파벳을 put 해주고 기존에 밟았는지 여부를 containsKey 메서드를 이용하고자 했습니다. 하지만 HashMap의 경우 객체기 때문에 재귀 탐색 시 다른 경로들과 자료를 공유하는 이슈가 있었습니다. 그리하여 성능이 나쁘더라도 String 문자열 객체를 사용했는데, 문제 설명에 명시된 시간 제한 조건을 초과하긴 했지만.. 통과될 수는 있었습니다.. 😅 (시간복잡도를 개선할 방법을 좀 더 생각해봐야할 것 같습니다.)

 

(2022. 7. 26. Update) 해당 문제는 백트래킹을 이용하여 시간 복잡도 성능을 개선시킬 수 있었습니다.(소스 코드 하단 참고)

※ 당초 3초 걸리는 것을 2초로 성능 개선

 

전체 소스 코드(단순 DFS)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    static int r, c, result = 0;
    static String[][] board;

    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());
        board = new String[r][c];

        for (int i = 0; i < r; i++) {
            board[i] = br.readLine().split("");
        }

        dfs(0, 0, 0, "");

        System.out.println(result);
    }

    public static void dfs(int x, int y, int count, String visited) {
        if (x < 0 || x > r - 1 || y < 0 || y > c - 1 || visited.contains(board[x][y])) {
            result = Math.max(count, result);
            return;
        }

        visited += board[x][y];
        count++;

        dfs(x + 1, y, count, visited);
        dfs(x - 1, y, count, visited);
        dfs(x, y + 1, count, visited);
        dfs(x, y - 1, count, visited);
    }
}

 

전체 소스 코드(백트래킹 적용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

class Main {

    static int r, c, result = 0;
    static char[][] board;
    static Set<Character> alphas = new HashSet<>();

    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());
        board = new char[r][c];

        for (int i = 0; i < r; i++) {
            board[i] = br.readLine().toCharArray();
        }

        dfs(0, 0, 0);

        System.out.println(result);
    }

    public static void dfs(int x, int y, int count) {
        if (x < 0 || x > r - 1 || y < 0 || y > c - 1) {
            return;
        }

        if (alphas.contains(board[x][y])) {
            result = Math.max(count, result);
            return;
        }

        alphas.add(board[x][y]);
        count++;

        dfs(x + 1, y, count);
        dfs(x - 1, y, count);
        dfs(x, y + 1, count);
        dfs(x, y - 1, count);

        alphas.remove(board[x][y]);
    }
}

 

참고자료

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