BOJ_G4_1987

📁 [G4_1987] 알파벳

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static StringTokenizer st;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int R, C;
    static boolean[][] isChecked;
    static int nx,ny;
    // 총 횟수 카운팅
    static int cnt;
    static int max = Integer.MIN_VALUE;
    static boolean[] alp;
    static char[][] arr;
    static int i =0;

    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine(), " ");

        // 세로
        R = Integer.parseInt(st.nextToken());

        // 가로
        C = Integer.parseInt(st.nextToken());

        // 입력값 저장
        arr = new char[R][C];

        // 지나갔는지 체크
        isChecked = new boolean[R][C];

        // 수 체크
        alp = new boolean[26];

        // 배열 입력
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                arr[i][j] = str.charAt(j);
            }
        }

        check(0,0);
        System.out.println(max);
    }

    static void check(int x, int y) {
        if(x < 0 || x == R || y < 0 || y == C ||  alp[(arr[x][y]-65)] == true) {
            return;
        }

        // 방문을 안했으면 true로 바꿔주고 하나 카운팅

        alp[(arr[x][y]-65)] = true;
        cnt++;

        max = Math.max(max, cnt);


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

            check(nx,ny);
        }
        alp[(arr[x][y]-65)] = false;
        cnt--;
    }
}

🤔 나의 생각

문제를 보고 먼저 순서가 상관이 있기 때문에 순열로 풀어야 겠다는 생각이 들었다.
그리고 알파벳이 사용되었는지 유무를 파악하기 위해 26개의 원소를 가진 boolean 배열과 계산을 아스키코드를 이용하여 0->A, 1->B .. 이런식으로 정해주었다.
그리고 재귀로 갔다와서는 백트래킹을 통해 좀 더 효율적인 코드를 작성하였다.
처음 위치부터 4방향 탐색을 통해 다음 원소를 정해주었다.
결론적으로는 DFS와 백트래킹에 대해 좀 더 공부하게 되는 문제였다.