[백준] 1987번 - 알파벳 [Java]

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

 

[백준] 1987번 - 알파벳 [Java]

[백준] 1987번 - 알파벳 [Java]

---

1.  아이디어

 

DFS 알고리즘과 Set을 활용한 방문체크로 간단하게 해결할 수 있고 칸이 알파벳으로만 이루어져있어서 비트마스킹을 활용한 방문체크로도 해결할 수 있다.

---

2. 문제풀이

 

DFS 탐색 과정에서 다른 노드 가지 탐색을 위해 방문 체크를 해제하는 점만 주의해서 구현하면 된다.

---

3. 코드

 

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

public class Main_DFS {

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    private static int R;
    private static int C;
    private static char[][] map;
    private static final Set<Character> set = new HashSet<>();
    private static int max = 0;

    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];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        dfs(0, 0);

        System.out.println(max);
    }

    private static void dfs(int r, int c) {
        set.add(map[r][c]);
        max = Math.max(max, set.size());

        for (int dir = 0; dir < 4; dir++) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if (set.contains(map[nr][nc])) continue;

            dfs(nr, nc);

            set.remove(map[nr][nc]);
        }
    }

}

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

public class Main_Bitmask {

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    private static int R;
    private static int C;
    private static char[][] map;
    private static int visited = 0;
    private static int max = 0;

    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];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        dfs(0, 0, 1);

        System.out.println(max);
    }

    private static void dfs(int r, int c, int depth) {
        visited |= 1 << (map[r][c] - 'A');
        max = Math.max(max, depth);

        for (int dir = 0; dir < 4; dir++) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if ((visited & (1 << (map[nr][nc] - 'A'))) != 0) continue;

            dfs(nr, nc, depth + 1);

            visited &= ~(1 << (map[nr][nc] - 'A'));
        }
    }

}

---

4. 후기

 

- DFS

- 비트마스킹