쫑쫑이의 블로그

백준 1987 알파벳 Java [DFS] 본문

알고리즘/백준

백준 1987 알파벳 Java [DFS]

쫑쫑2 2022. 11. 12. 17:24

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

 

1987번: 알파벳

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으

www.acmicpc.net

 

알파벳을 아스키코드로 바꿔서 65씩 빼주면 0 ~ 25 사이의 숫자로 표현 가능하다

크기가 26인 방문 배열을 만들어 알파벳 방문체크해가면서 dfs로 탐색하면 된다

 

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

public class Main {
    static int count, X, Y;
    static boolean[] vtd;
    static int[][] chart;
    static Point[] dir = new Point[]{new Point(1, 0), new Point(-1, 0), new Point(0, -1), new Point(0, 1)};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());
        vtd = new boolean[26];
        chart = new int[X][Y];
        count = 0;
        for (int x = 0; x < X; x++) {
            chart[x] = br.readLine().chars().map(e -> e-65).toArray();
        }
        vtd[chart[0][0]] = true;
        dfs(0, 0, 1);
        System.out.println(count);
    }
    static void dfs(int x, int y, int cnt) {
        if (cnt > count) count = cnt;
        for (Point p : dir) {
            int nx = p.x + x, ny = p.y + y;
            if (isRange(nx, ny) && !vtd[chart[nx][ny]]) {
                vtd[chart[nx][ny]] = true;
                dfs(nx, ny, cnt + 1);
                vtd[chart[nx][ny]] = false;
            }
        }
    }

    static boolean isRange(int x, int y) {
        return (x >= 0 && y >= 0 && x < X && y < Y) ? true : false;
    }
}