[백준] 1987번 자바 알파벳

문제 출처 

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

1987번: 알파벳

 

 

 

접근 방식 및 풀이

- BFS, DFS 모두 사용가능하지만, BFS는 알파벳의 방문여부를 체크하기 까다롭다. 이부분에서 해매다가 결국 DFS 알고리즘을 적용하여 해결하였다.

 

 

 

 

소스 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
 
public class Main {
 
    static char[][] map;
    static boolean[] visitcheckdfs;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    static int R, C;
    static int ans =1;
    static int cnt =1;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        C = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        map =new char[C][R];
        dist =new int[C][R];
        visited = new boolean[C][R];
        visitcheckdfs = new boolean[26];
 
        for (int i = 0; i < C; i++) {
            String input = br.readLine();
            for (int j = 0; j < R; j++) {
                map[i][j] = (char) (input.charAt(j) - 'A');
            }
        }
 
        dfs(map, visitcheckdfs, 0,0);
        System.out.println(ans);
    }
    
    private static void dfs(char[][] map, boolean[] visited , int x, int y){
        int idx = map[x][y];
        visited[idx] = true;
 
        for (int i = 0; i <4 ; i++) {
            int next_x = x + dx[i];
            int next_y = y + dy[i];
            if(next_x>=0 && next_y>=0 && next_x < C&& next_y < R ){
                int tmpnextxy = map[next_x][next_y];
                if(!visitcheckdfs[tmpnextxy]){
                    ans = Math.max(++cnt, ans);
                    dfs(map, visitcheckdfs, next_x, next_y);
                }
            }
        }
        --cnt;
        visitcheckdfs[idx] = false;
    }
 
}

 

 

결과