[BOJ] 1987 알파벳 - JAVA

1. 문제

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

1987번: 알파벳

• 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
• 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
• 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

---

2. 풀이

출발하기 전에 내 위치에 있는 알파벳을 check 배열에 true로 마킹한다.

한 칸 움직였다는 의미이므로 현재 result와 내 cnt+1을 비교한다. +1을 하는 이유는, cnt는 인덱스 기반인데 result는 횟수를 저장하기 때문이다. 

4방향으로 탐색을 하면서 다음 위치로 갈 수 있다면 재귀호출한다.

갈 수 있는지 판단은 1) 범위에 벗어나지 않는지 2) check배열에 저장되어있는 알파벳 중 나와 동일한 것이 있는지 로 확인한다. (board[r][c]-'A'로 바로 확인 가능)

탐색이 끝났다면 해당 알파벳을 다시 false 상태로 되돌려준다.

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

public class BOJ_1987_알파벳 {
    static int R, C, result;
    static char[][] board;
    static boolean[] check;
    static int[][] deltas = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};//상-좌-하-우

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        board = new char[R][C];

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

        //함수 호출하기
        check = new boolean[26];
        move( 0,0, 0);

        //출력하기
        System.out.println(result);


    }

    private static void move(int cnt, int r, int c) {
        check[board[r][c]-'A'] = true;
        result = Math.max(result, cnt + 1);

        for (int d = 0; d < 4; d++) {
            int nr = r + deltas[d][0];
            int nc = c + deltas[d][1];

            if (isAvailable(nr, nc)) move(cnt + 1, nr, nc);
        }
        check[board[r][c]-'A'] = false;

    }

    private static boolean isAvailable(int nr, int nc) {
        if (nr < 0 || nr >= R) return false;
        if (nc < 0 || nc >= C) return false;
        if(check[board[nr][nc]-'A']) return false;

        return true;
    }
}

원래 check배열을 boolean으로 하지 않고 char[]로 해서 cnt마다 하나씩 채워줬다. 하지만 그렇게 하니 매번 반복문으로 동일한 알파벳이 이미 있는지 확인해야 했다. 기록용으로 남겨본다.

    //이동 함수
    private static void move(int cnt, int r, int c) {
        check[cnt] = board[r][c];
        result = Math.max(result, cnt + 1);

        for (int d = 0; d < 4; d++) {
            int nr = r + deltas[d][0];
            int nc = c + deltas[d][1];

            if (isAvailable(cnt, nr, nc)) move(cnt + 1, nr, nc);
        }

    }

    //해당 위치가 가능한지 체크하는 함수
    private static boolean isAvailable(int cnt, int nr, int nc) {
        if (nr < 0 || nr >= R) return false;
        if (nc < 0 || nc >= C) return false;

        for (int i = 0; i <= cnt; i++) {
            if (check[i] == board[nr][nc]) return false;
        }

        return true;
    }

---

3. 결과

첫번째가 반복문 사용 코드, 두번째는 수정하다가 한 번 틀린 코드(ㅎㅎ), 마지막이 boolean배열을 사용해서 한번에 접근한 코드다. 두 배 정도 빨라졌다!