[백준 / JAVA] 1987. 알파벳 (G4)

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

 

싸피 때 비슷한 문제를 풀었던 기억이 있다. 벽 부수고 이동하기 시리즈인데 핵심은 탐색을 할 때 탐색하는 주체에 상태를 저장하는 것이다. 이 문제에선 해당 알파벳을 지났는지 여부를 배열로 객체 안에 넣었다. 이제 골드 문제 4개를 날먹할 수 있을 것이다.

 

bfs와 dfs

 

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        mapR = Integer.parseInt(st.nextToken());
        mapC = Integer.parseInt(st.nextToken());
        map = new char[mapR][mapC];
        for (int i = 0; i < mapR; i++)
            map[i] = br.readLine().toCharArray();
        dfs(new Point(0, 0, new boolean[26], map[0][0]), 1);
        System.out.println(max);
    }

    static char map[][];
    static int mapR, mapC, max = 0, dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };

    static void dfs(Point cur, int step) {
        max = Math.max(step, max);
        for (int d = 0; d < 4; d++) {
            int nr = cur.row + dr[d];
            int nc = cur.col + dc[d];
            if (nr < 0 || nr >= mapR || nc < 0 || nc >= mapC || cur.alphabet[(int) map[nr][nc] - 65]) // 지나간 알파벳
                continue;
            dfs(new Point(nr, nc, cur.alphabet, map[nr][nc]), step + 1);
        }
    }

    static class Point {
        int row, col;
        boolean alphabet[];

        public Point(int row, int col, boolean[] alphabet, char c) {
            super();
            this.row = row;
            this.col = col;
            this.alphabet = Arrays.copyOf(alphabet, 26);
            this.alphabet[(int) c - 65] = true;
        }
    }
}