[백준] 🥇 1987 알파벳

📌 난이도

🥇 Gold 4

📌 문제

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

📌 풀이

모든 문제를 BFS로 풀 수 있다고 자신만만하던 때에 정신적인 충격을 준 문제였다.
BFS로 이 문제를 구현하려면 중복이 너무나도 많이 발생하여, 메모리초과가 뜰 수 밖에 없는 문제였다.
따라서, 처음으로 재귀함수를 이용하여 DFS를 구현해 보았다.

📌 Code

package BOJ.DFS;

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

public class N1987 {
    static int R;
    static int C;
    static int[][] board;
    static boolean[] visited;
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, 1, 0, -1};
    static int max;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        board = new int[R][C];
        visited = new boolean[26];
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                board[i][j] = str.charAt(j) - 'A';
            }
        }
        max = 0;
        DFS(0, 0, 0);
        System.out.println(max);
    }

    static void DFS(int r, int c, int count) {
        if (visited[board[r][c]]) {
            max = Math.max(max, count);
            return;
        } else {
            visited[board[r][c]] = true;
            for (int i = 0; i < DR.length; i++) {
                int nextR = r + DR[i];
                int nextC = c + DC[i];
                if (nextR < 0 || nextR >= R || nextC < 0 || nextC >= C) {
                    continue;
                }
                DFS(nextR, nextC, count + 1);
            }
            visited[board[r][c]] = false;
        }
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁