문제 설명

R행 C열 보드가 있음. 여기서 각 칸마다 알파벳이 하나 적혀있음. 현재 위치에서 상하좌우로 이동 가능.
한 번 지난 적 있는 알파벳은 다시 지나면 안됨.
보드 내 좌상단에서 시작해서 이동할 수 있는 최대 횟수는?

문제 접근

처음에는 최소인줄 알고 bfs로 풀려했으나 문제를 다시보니 최대 이동 칸 수를 구하는 문제였다.
때문에 dfs를 선택했다.
매우 전형적인 dfs문제지만 isVisited뿐 아니라 이미 지났던 알파벳인지도 여부를 검사할 수 있어야 한다. 나는 그냥 불리언 배열을 하나 더 배치했다.

풀이

import java.util.*;
import java.io.*;

public class Main {
    static int R, C;
    static char[][] graph;
    static boolean[] isCharVisited = new boolean[100];
    static boolean[][] isVisited;

    static int max = 0;
    static int[][] directions = {
            {0, 1},
            {0, -1},
            {1, 0},
            {-1, 0}
    };

    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());

        graph = new char[R + 1][C + 1];
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                graph[i + 1][j + 1] = line.charAt(j);
            }
        }
        isVisited = new boolean[R + 1][C + 1];

        isVisited[1][1] = true;
        isCharVisited[graph[1][1]] = true;
        dfs(1, 1, 1);
        System.out.println(max);
    }

    static void dfs(int curR, int curC, int curDistance) {
        max = Math.max(max, curDistance);
        for (int[] direct : directions) {
            int nextR = curR + direct[0];
            int nextC = curC + direct[1];
            if (nextR >= 1 && nextR <= R &&
                    nextC >= 1 && nextC <= C &&
                    !isCharVisited[graph[nextR][nextC]] &&
                    !isVisited[nextR][nextC]) {
                isVisited[nextR][nextC] = true;
                isCharVisited[graph[nextR][nextC]] = true;
                dfs(nextR, nextC, curDistance + 1);
                isCharVisited[graph[nextR][nextC]] = false;
                isVisited[nextR][nextC] = false;
            }
        }
    }

}

비트마스킹 풀이법

답은 맞았지만 그냥 다른 사람들의 풀이가 궁금해서 확인하려고 봤는데 여기서 알파벳 방문 여부를 비트마스킹으로 해결한 사람들이 꽤 있었다.
우선 이게 가능한 이유는 알파벳이 26개라서 2의 26승이 약 6000만대라서 인트형 범위 내에 들어오기 때문이다.
이렇게 하면 int형 한개에 방문 여부를 저장할 수 있으므로 메모리적으로 훨씬 절약이라 괜찮은 방법 같았다.

느낀점

오랜만에 dfs풀어서 반가웠고, 무엇보다 java에서 char -> int 를 오랜만에 변환해본 것 같다. 또 비트마스킹 기법으로 메모리 절약하는 것도 익힐 수 있었다.

헉 골드2를 달성했다...

클래스 4문제를 다 풀었더니 점수가 크게 오른듯 싶다. 이렇다면 방학 목표인 골드1이 가능할지도 모르겠다.