[백준 1987] 알파벳 / 자바 / 백트래킹

문제         

레벨: G4
알고리즘: 백트래킹
풀이시간: 30분
힌트 참조 유무: 무

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

1 번째 시도   

백트래킹 기본적인 문제
굳이 설명을 적지 않겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    static int ans = Integer.MIN_VALUE;
    static boolean[][] visited;
    static int[] dx = {1,0,0,-1};
    static int[] dy = {0,1,-1,0};
    static int R,C;
    static String[][] arr;

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

        String[] s = br.readLine().split(" ");
         R = Integer.parseInt(s[0]);
         C = Integer.parseInt(s[1]);

        visited = new boolean[R][C];

         arr = new String[R][C];

        for(int i =0; i <R; i++) {
            String[] s1 = br.readLine().split("");
            for(int j = 0; j < C; j++) {
                arr[i][j] = s1[j];
            }
        }
        visited[0][0] = true;
        dfs(0,0,arr[0][0], 1);

        System.out.println(ans);
    }

    public static void dfs(int x, int y, String history, int cnt) {
        ans = Math.max(Main.ans, cnt);

        for(int i = 0; i < 4; i++) {
            int nx = x+ dx[i];
            int ny = y+ dy[i];

            if(nx <0 || nx >= C || ny <0 || ny >=R )
                continue;
            if(visited[ny][nx] || history.contains(arr[ny][nx]))
                continue;

            visited[ny][nx] = true;
            dfs(nx,ny,history+arr[ny][nx], cnt+1);
            visited[ny][nx] = false;
        }
    }

}