[백준][1987번: 알파벳]

🎯문제

문제링크

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

🎯입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다

🎯출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

🎯접근방법

1. dfs 재귀방법을 통해서 상하좌우를 살핀 후 같은 알파벳을 지나왔나 확인 후 재귀를 돌게 하였다.

🎯코드

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

public class Main {
    static int R,C;
    static char[][] map;
    static int[] mx = {-1,1,0,0};
    static int[] my = {0,0,-1,1};
    static int ans;
    static ArrayList<Character> arr;
    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 char[R+1][C+1];

        for(int i=1; i<=R; i++){
            String str = br.readLine();
            for(int j=1; j<=C; j++){
                map[i][j] = str.charAt(j-1);
            }
        }
        arr = new ArrayList<>();
        dfs(1,1);
        System.out.println(ans);
    }
    static void dfs(int x, int y){
        if(arr.contains(map[x][y])){
            ans = Math.max(ans,arr.size());
            return;
        }else {
            arr.add(map[x][y]);
            for (int i = 0; i < 4; i++) {
                int px = x + mx[i];
                int py = y + my[i];
                if (px > 0 && py > 0 && px <= R && py <= C) {
                    dfs(px, py);
                }
            }
            arr.remove(arr.size() - 1);
        }
    }
}

🎯 알고 넘어가기

저는 처음에 ArrayList를 만들어서 지금까지 지난온 알파벳을 기억하고 다시 돌아갈 때 지우고 하는 방식으로 하였습니다. 지울 때 remove를 하면서 O(N) 시간복잡도를 잡아 먹기 때문에 시간적으로 오래걸리는 것을 알게되었다. 그래서 boolean 배열로 알파벳 개수만큼 할당을 하여 true/false 알파벳을 사용하는지 안하는지 코딩을 했다. 그 결과 ArrayList로 했을 때랑 로직은 비슷한데 보다 속도면에서 효율적이다.