boj 1987 알파벳

www.acmicpc.net/problem/1987

1987번: 알파벳

 

문제에서 요구하는 조건은

1. 말은 (0, 0)에서 출발합니다.

2. 말은 상하좌우 방향으로 움직일 수 있습니다.

3. 말이 지나가는 동안 밟은 칸의 알파벳은 모두 달라야합니다.

 

말이 (0, 0)에서 출발하여 지나갈 수 있는 최대의 칸 수를 출력해야합니다.

저는 백트래킹으로 해결하였고 해당 칸을 방문체크하는 visit배열과 칸에 있는 알파벳 중복체크를 위한 alphachk 배열을 사용하였습니다.

 

재귀를 돌릴때마다 답을 갱신해주고, 해당 칸과 알파벳에 방문처리합니다.

그 다음 4방향 탐색하여 맵 밖으로 나갔는지, 이미 방문하였거나 밟은 적이 있는 알파벳인지 체크를 해줍니다.

모두 통과하면 nx, ny, cnt+1를 재귀로 넘겨주고, 빠져나오면 true했던 boolean배열을 모두 false로 바꿔줍니다.

마지막으로 정답을 출력합니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static boolean visit[][], alphachk[];
    static char list[][];
    static int N, M, ans;
 
    static void dfs(int x, int y, int cnt) {
        ans = Math.max(ans, cnt);
        visit[x][y] = true;
        alphachk[list[x][y] - 'A'] = true;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                continue;
            if (visit[nx][ny] || alphachk[list[nx][ny] - 'A'])
                continue;
 
            dfs(nx, ny, cnt + 1);
            alphachk[list[nx][ny] - 'A'] = false;
            visit[nx][ny] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new char[N][];
        visit = new boolean[N][M];
        alphachk = new boolean[26];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0, 0, 1);
        System.out.println(ans);
    }
}