[백준(Baekjoon)] 1987. 알파벳 (java, DFS)

안녕하세요. 오늘은 백준의 1987. 알파벳 문제를 풀어보겠습니다.

1. 문제 링크

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

2. 문제 풀이

✔️ 탐색 이용: BFS, DFS?

문제를 보자마자 "탐색을 이용해야겠다"라는 생각이 들었습니다. BFS를 이용할지, DFS를 이용할지 선택해야 하는데, BFS는 넓게 탐색을 진행하는 방식이므로 직전에 어떤 행과 열을 다녀왔는지 알기가 어렵습니다. 따라서 DFS를 이용해 문제를 풀어주면 됩니다.

3. 전체 코드

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

public class Main {
    private static final int[] dr = {-1, 1, 0, 0};
    private static final int[] dc = {0, 0, -1, 1};
    
    private static int R;
    private static int C;
    private static int answer;
    private static char[][] map;
    private static boolean[][] visited;
    private static Set<Character> moveSet;

    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());

        map = new char[R][C];
        visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        answer = 1;
        moveSet = new HashSet<>();
        moveSet.add(map[0][0]);
        visited[0][0] = true;

        dfs(0, 0, 1);

        System.out.println(answer);
    }

    private static void dfs(int sr, int sc, int tmp) {
        for (int d = 0; d < 4; d++) {
            int nr = dr[d] + sr;
            int nc = dc[d] + sc;

            if (nr < 0 || nc < 0 || nr >= R || nc >= C) {
                continue;
            }

            if (visited[nr][nc]) {
                continue;
            }

            if (moveSet.contains(map[nr][nc])) {
                continue;
            }

            moveSet.add(map[nr][nc]);
            visited[nr][nc] = true;
            dfs(nr, nc, tmp + 1);
            visited[nr][nc] = false;
            moveSet.remove(map[nr][nc]);
        }

        answer = answer > tmp ? answer : tmp;
    }
}

4. 느낀점

✔️ 틀렸던 이유

• answer 를 초기화하지 않음(answer = 1; 없었음)
• dfs 쪽에서, int nc = dr[d] + sc; 로 실수했음 -> dr[d]가 아닌, dc[d]로 고침

바보같이 실수해서 틀렸다. 저런 실수 다시는 하지 말아야겠다..