백트래킹. 알파벳

문제

세로 R칸(row)
가로 C칸(column)
각 칸에는 알파벳 대문자가 적혀있음.
좌측상단에는 말이 놓여져있음.
말은 상하좌우로 이동할수있고, 새로 이동한 칸에는 지금까지 지나쳐온 알파벳과
달라야한다. 같은 알파벳이 적힌칸은 두번 지날수없다.
좌측상단부터 시작해서, 최대 몇칸 갈수있는지 프로그램 작성.
1. R,C(20이하)
2. 알파벳들이 빈칸없이 주어짐.
출력 : 최대 칸 수 출력

해결방향성

기본적으로 DFS 탐색, 그러나 여태 지나온 알파벳을 지나면 안되니, visited 배열 필요, 또한, 되돌아올때 false시켜주어야하므로 백트래킹.

코드

package backTracking;

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.StringTokenizer;

public class Alphabet {
    static int R, C;
    static char[][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                board[i][j] = str.charAt(j);
            }
        }

        boolean[] visitAlpha = new boolean[26];
        // 현재 발판을 미리 visited 하고 시작
        visitAlpha[board[0][0] - 'A'] = true;
        // 처음 발판 포함이니 count = 1부터 시작
        DFS(1,0,0, visitAlpha);

        bw.write(String.valueOf(max));


        bw.flush();
        br.close();
        bw.close();
    }

    // ㄴㄴ 상하좌우 다필요하고 visited 체크해야한다.
    private static int[] dx = {1, 0,-1,0}; // 하, 우
    private static int[] dy = {0, 1,0,-1};

    private static void DFS(int count, int x, int y, boolean[] visitAlpha) {
        // 현재 컬러
        char color = board[x][y];
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            // 범위 안에없으면 continue;
            // 여태까지 컬러랑 일치하면 continue;
            // 중복 방문 체크 -> 근데 이거 color로 해결될듯
            if (!check(newX, newY)
                    || isSame(board[newX][newY], visitAlpha)){
                continue;
            }
            // 범위 안에 있고, 컬러가 다르면
            // 백트래킹 대칭
            visitAlpha[board[newX][newY] - 'A'] = true;
            DFS(count + 1, newX, newY, visitAlpha);
            visitAlpha[board[newX][newY] - 'A'] = false;
        }
        // 종료조건은 만족하는 조건이 없을때 나오므로 여기서 max값 저장
        max = Math.max(count, max);
    }

    private static int max = 0;
    private static boolean isSame(char color, boolean[] visitAlpha) {
        // hashset을 사용하는것보다 visitAlpha를 사용해서 A~Z까지 방문여부를 넣는게
        // 시간이 훨씬 덜걸릴 것으로 예상. hashset은 시간이 보기보다 오래걸린다
        // hashset 작동방식을 조사하면 좋을듯.
        for (int i = 0; i < 26; i++) {
            if (visitAlpha[color - 'A']) {
                return true;
            }
        }
        return false;
    }

    private static boolean check(int newX, int newY) {
        return 0 <= newX && newX < R && 0 <= newY && newY < C;
    }
}

결론

• 4방, 8방 방식 형식화 필요. -> 근데 많이 풀어보는게
• 백트래킹 대칭형 숙달 필요 -> 역시 많이 풀어보는게