[알고리즘] 백준 > #1987. 알파벳

문제링크

백준 #1987. 알파벳

풀이방법

주어진 조건들을 보고 바로 백트래킹을 활용하는 문제라고 생각했다. 일반적인 백트래킹 문제 풀이와 같이 갈 수 있는 경로라면 해당 경로를 왔음을 어딘가에 저장하고 다시돌아와서는 그 표시를 되돌려놨다. 보통 백트래킹 문제에서는 map 내의 각 위치에 대해서 visited 변수를 사용해 이미 지나온 경로인지 확인을 했는데 이 문제에서는 이미 사용된 알파벳인지 확인하는 check 변수로 충분히 확인 가능했다! 쉬운문제였다~

코드

import java.util.*;

public class BOJ1987 {

    static int r, c;
    static char[][] map = new char[20][20];
    static int maxCount = 0;
    static boolean[] check = new boolean[26];

    static int[] dy = {0, 0, -1, +1};
    static int[] dx = {-1, +1, 0, 0};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        r = sc.nextInt();
        c = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i < r; i++) {
            String temp = sc.nextLine();
            map[i] = temp.toCharArray();
        }

        searchMaxCount(0, 0, 1);
        System.out.println(maxCount);
    }

    private static void searchMaxCount(int y, int x, int count) {
        check[map[y][x] - 'A'] = true;

        for (int i = 0; i < 4; i++) {
            int nextY = y + dy[i];
            int nextX = x + dx[i];
            if (isInRange(nextY, nextX) && !check[map[nextY][nextX] - 'A']) {
                searchMaxCount(nextY, nextX, count + 1);
                check[map[nextY][nextX] - 'A'] = false;
            }
        }

        if (count > maxCount) maxCount = count;
    }

    private static boolean isInRange(int y, int x) {
        return ((y >= 0) && (y < r) && (x >= 0) && (x < c));
    }
}