[JAVA] 백준 1987 - 알파벳

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.function.BiPredicate;

public class Main {
    static int alpha = 'A';
    static int max = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        char[][] map = new char[a[0]][a[1]];
        for (int i = 0; i < map.length; i++) {
           map[i] = br.readLine().toCharArray();
        }
        boolean[] visited = new boolean[26];
        dfs(map,visited,0,0,"");
        System.out.println(max);
    }

    static void dfs(char[][] map, boolean[] visited, int i, int j, String ans){
        char c = map[i][j];
        visited[getIdx(map,i,j)] = true;
        ans +=c;
        max = Math.max(max,ans.length());
        if(check(map,visited.clone(),i+1,j)) dfs(map, visited.clone(), i+1,j, ans);
        if(check(map,visited.clone(),i-1,j)) dfs(map, visited.clone(), i-1,j, ans);
        if(check(map,visited.clone(),i,j+1)) dfs(map, visited.clone(), i,j+1, ans);
        if(check(map,visited.clone(),i,j-1)) dfs(map, visited.clone(), i,j-1, ans);
    }

    static boolean check(char[][] map, boolean[] visited, int i, int j){
        BiPredicate<Integer, Integer> check = (a,b)->a>=0&&a<map.length&&b>=0&&b<map[0].length;
        return check.test(i,j)&&!visited[getIdx(map,i,j)];
    }

    static int getIdx(char[][] map,int i, int j){
        return map[i][j]-alpha;
    }
}

전형적인 DFS 문제이다. (0,0)에서 시작해서 알파벳으로 이루어진 경로를 알파벳이 겹치지 않게 이동할 수 있는 최대 거리를 구하는 문제이다.

상하좌우로 이동가능한지 체크하며 이동한 경우 알파벳 방문 체크 배열 visited를 업데이트하는 것을 반복하며 최대 이동 거리를 구했다.

왜 골드4인지 모르겠지만 한번에 맞춰서 기분이 좋다.