백준 1987 알파벳(DFS)

문제 접근

- 같은 알파벳을 만나지 않을 최대 경우의 수를 구하는 문제

- 탐색을 시작할 때에 hash.add를 해주고, 탐색을 완료했을 때에 hash.remove를 해주어 계속해서 누적되지 않도록 한다. 

(만약 누적되면 다른 방향으로 진행할 때에 이전에 탐색한 값 때문에 중복되어 탐색할 수가 없다)

 

헷갈렸던 부분

- visited 배열을 운영할 필요가 없었다. 왜냐하면 HashSet에서 같은 문자인지를 체크해주기 때문이다.

- 탐색을 시작할때 add, 완료했을 때에 remove 해주는 부분을 for문 안에서 구현했었는데 오히려 복잡해져서 for문 밖으로 빼주었다. 

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

public class Main {
    public static void main(String[] args) throws IOException {
        solution();
    }
    static int R;
    static int C;
    static char[][] arr;
    static boolean[][] visited;
    static HashSet<Character> hash;
    static int max;
    static class People{
        int x;
        int y;
        int cnt;

        public People(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }

    public static void solution() 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());
        arr = new char[R][C];
        visited = new boolean[R][C];
        max = -1;
        for(int i=0; i<R; i++){
            String str = br.readLine();
            for(int j=0; j<C; j++){
                arr[i][j] = str.charAt(j);
            }
        }

        hash = new HashSet<>();

        People people = new People(0, 0, 0);
        dfs(people);
        System.out.println(max);
    }

    public static void dfs(People people){
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        if(hash.contains(arr[people.x][people.y])){
            max = Math.max(max, people.cnt);
            return;
        }

        hash.add(arr[people.x][people.y]);

        for(int i=0; i<4; i++){
            int nx = people.x + dx[i];
            int ny = people.y + dy[i];

            // 범위를 벗어나면
            if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            dfs(new People(nx, ny, people.cnt+1));
        }
        hash.remove(arr[people.x][people.y]);
    }
}