문제 바로가기

나의 풀이

경로에 따른 weight 라던지 value 값이 따로 없었던 기본적인 dfs 문제였다. 따라서 stack 과 같은 다른 자료구조들을 굳이 쓸 필요가 없었다.

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

class Main {

    static int r, c;
    // 문자를 그대로 담을 map
    static char[][] map;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int max = 0;
    // 특정 (x,y) 위치의 방문과 특정 문자를 방문했는 지, 2가지를 모두 해결
    static boolean[] visited = new boolean[26];

    public static void main(String[] args) throws IOException {
        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        map = new char[r][c];

        for (int i = 0; i < r; i++) {
            char[] chars = br.readLine().toCharArray();
            map[i] = chars;
        }

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

    public static void dfs(int x, int y, int count) {
        if (visited[map[x][y] - 'A']) {
            max = Math.max(max, count);
            return;
        } else {
            visited[map[x][y] - 'A'] = true;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                dfs(nx, ny, count + 1);
            }
            // 백트래킹의 핵심 포인트
            visited[map[x][y] - 'A'] = false;
        }
    }
}