[백준](Java) 1987 - 알파벳

문제 링크

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

문제 풀이

중복되는 알파벳을 찾기위해서 map을 사용했다. 새로운 칸에 접근할때 그 값이 이미 map에 저장되어 있다면 answer의 값을 구하고 다시 되돌아가는 방법을 선택했다.

다음 dfs를 넘겨주기 전에 chk, storage의 값을 변경시켜주고
dfs가 끝나고 왔을때는 storage값과 chk 값을 원래값으로 돌려준다.

코드

import java.sql.SQLOutput;
import java.util.*;

public class Main {

    static int n;
    static int m;
    static String[][] map;
    static int[] diry = {-1, 0, 1, 0};
    static int[] dirx = {0, 1, 0, -1};

    static int answer = 0;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new String[n][m];
        Map<String, Integer> storage = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String[] line = sc.next().split("");
            map[i] = line;
        }
        dfs(0, 0, 1, new boolean[n][m], storage);
        System.out.println(answer);
    }

    public static void dfs(int y, int x, int ans, boolean[][] chk, Map<String, Integer> storage) {
        chk[0][0] = true;
        storage.put(map[0][0],0);

        for (int i = 0; i < 4; i++) {
            int now_y = y + diry[i];
            int now_x = x + dirx[i];
            if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < m) {
                if (!chk[now_y][now_x]) {
                    if (!storage.containsKey(map[now_y][now_x])) {
                        chk[now_y][now_x] = true;
                        storage.put(map[now_y][now_x], 0);
                        dfs(now_y, now_x, ans + 1, chk, storage);
                        storage.remove(map[now_y][now_x]);
                        chk[now_y][now_x] = false;
                    } else {
                        answer = Math.max(answer, ans);
                    }
                } else {
                    answer = Math.max(answer, ans);
                }
            }
        }
        return;
    }
}