[BOJ] 1987 - 알파벳

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1987

1987번: 알파벳

난이도: 골드 4

사용언어: JAVA

 

풀이

이 문제는 재귀를 이용한 dfs를 이용하여 해결할 수 있습니다. dfs에 관한 기본적인 내용은 아래 문제의 풀이에서 볼 수 있습니다.

 

jooona.tistory.com/65

[BOJ] 1303 - 전쟁 - 전투

 

우선 이미 지나온 알파벳을 체크하기 위해 boolean 배열을 만들어주고, 해당 알파벳을 지나갈 때마다 true로 표시해줍니다. 그리고 더 이상 나아갈 수 없는 상황에 마주하면, 지나온 알파벳들을 다시 false로 바꿔줌으로써, 다른 경로에서 해당 알파벳을 지나갈 수 있도록 해줍니다.

 

import java.io.*;
import java.util.StringTokenizer;
 
class Main {
 
    static class position {
        int x;
        int y;
        int cnt = 1;
    }
 
    static int max = 1;
    static int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 네 가지 방향
    static boolean[] visit = new boolean[26]; // 알파벳의 사용 유무
 
    public static void dfs(position p, char arr[][]) {
        int i;
        visit[arr[p.x][p.y] - 'A'] = true; // 해당 알파벳을 지나왔다고 체크해주고
        for (i = 0; i < 4; i++) {
            if (arr[p.x + d[i][0]][p.y + d[i][1]] != 0 && visit[arr[p.x + d[i][0]][p.y + d[i][1]] - 'A'] == false) { // 지나온 알파벳이 아니면,
                position p1 = new position();
                p1.x = p.x + d[i][0];
                p1.y = p.y + d[i][1];
                p1.cnt = p.cnt + 1; // 카운트 +1
                max = Math.max(p1.cnt, max); // 혹시 max보다 cnt가 크다면 max값 업데이트
               dfs(p1, arr); //dfs 수행
                visit[arr[p.x + d[i][0]][p.y + d[i][1]] - 'A'] = false; // dfs에서 빠져나가면서 해당 알파벳을 안지나간 것으로 처리
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int i, j;
        char[][] arr = new char[R + 2][C + 2];
 
        String s;
        for (i = 1; i <= R; i++) {
            s = br.readLine();
            for (j = 1; j <= C; j++) {
                arr[i][j] = s.charAt(j - 1);
            }
        }
 
        position p = new position();
        p.x = 1;
        p.y = 1;
       dfs(p, arr); // (1,1)부터 시작
        System.out.println(max);
    }
}