<Algorithm> 33. 1987번 알파벳

1. 1987번 알파벳

• 백트래킹 문제, 단순 DFS는 영역을 구할 때 사용한다. 즉 한번의 경우가 아닌 갈 수 있는 모든 곳을 탐색 하는 것이다.

• 이 경우는 하나의 경로에 하나의 답이 필요한 문제로 하나의 경로가 끝나면 다시 이전 경로로 돌아가 탐색해야한다.

• 하나의 경로가 끝나는 경우 그 경로에 해당하는 값은 없애주어야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int res = Integer.MIN_VALUE;
    static int count = 0;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        boolean[] visited = new boolean[1000];
        
        char arr[][] = new char [R][C];
        for(int i = 0; i < R; i++) {
          String temp = br.readLine();
          for(int j = 0; j < C; j ++) {
              arr[i][j] = temp.charAt(j);
          }
        }
        name(arr, 0, 0, R, C,visited);
        
        System.out.println(res + 1);// 첫번째 경우 추가
    }
    
    public static void name(char arr[][],int x,int y,int R,int C, boolean[] visited){
        
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        
        visited[arr[x][y]] = true; // 한번 갔던 알파벳 표시
        
        for(int i = 0; i < dx.length ; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && ny >= 0 && nx < R && ny < C ) {
                if(!visited[arr[nx][ny]]) {
                    count++;
                    name(arr, nx, ny, R, C,visited);
                }
                
                if(res < count) {
                    res = count; // 최대값 저장
                }
            }
        }
        visited[arr[x][y]] = false;
        // 백트래킹이 발생하게 되면 이 경우에서 방문했던 알파벳은 방문하지 않은게 되므로
        // 방문 안함으로 바꿔 주어야한다.
        count--;
        // 방문 안했으니 다시 제자리로..
        
    }
}