[백준] 1987번 알파벳 (비트마스크로 풀기)

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

 

문제는 그냥 평범한 dfs 문제임,, 그치만 메모리랑 시간이 오바라서 개선을 좀 해봤음

메모리 사용량이나 시간이나 많이 개선 되었음. 

 

핵심은 비트 마스킹!!

 

원래 작성했던 코드이다. 

문제에서는 이동했던 알파벳으로는 이동이 불가하다. 즉, 이동했던 경로에 있던 알파벳을 계속 기억하고 있어야한다.

이를 위해 해시셋을 사용하여서 거쳐왔던 알파벳 정보를 저장했다. 

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

public class Main {

    public static int r,c;
    public static HashSet<Character> hs = new HashSet<>();
    public static char map[][];
    public static int dx[]= {0,0,-1,1};
    public static int dy[]= {-1,1,0,0};
    public static int max = 0;

    public static boolean inRange(int x, int y){
        return x >= 0 && y >= 0 && x < r && y <c;
    }

    public static void dfs(int x, int y, int depth){
        boolean moved = false;
        // 상하좌우 탐색 & 재귀
        for (int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (inRange(nx,ny) && !hs.contains(map[nx][ny])){// 이동 가능하다면
                moved = true;
                hs.add(map[nx][ny]);
                dfs(nx,ny,depth+1);
                hs.remove(map[nx][ny]);
            }

            if(!moved){ // 더 이상 이동 불가한 경우, 해당 경로까지의 값을 기준으로 최댓값 업데이트
                max = Math.max(max, depth);
            }
        }

    }


    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++){
            String str = br.readLine();
            for (int j = 0; j < c; j++){
                map[i][j] = str.charAt(j);
            }
        }

        hs.add(map[0][0]);
        dfs(0,0,1); // 상하좌우 탐색 시작.

        System.out.println(max);
    }
}

 

내 코드의 문제? 

1. 해시셋의 경우 이론상 시간복잡도는 O(1)이다.

하지만 실제로는 해시값을 계산하는 시간 + 충돌 시 해결 시간(체이닝 or 리해싱) 등의 시간도 소요된다.  

 

2. 또한 해시셋은 원시타입(primitive) 사용이 불가하다. 따라서 해시셋은 Character인 wrapper타입을 사용한다.

내 코드 상에서는 map에 있는 값은 char (원시타입), 해시셋에 알파벳을 add할 때에는 Character를 사용하므로 '오토박싱' 작업이 추가로 들어가서 그만큼의 시간도 소요된다. 

 

3. 또한 메모리 관점에서도, 해시셋은 GC가 많이 발생한다. 

해시셋은 배열 + 리스트/트리로 구성된다. (기존에는 배열이지만, 충돌 발생 시에 리스트/트리 사용함)

이런 구조에서 remove가 발생하면, 그만큼 GC로 삭제할 내용도 많아진다.

만약 DFS가 수천, 수만번,,, 그 이상으로 많이 수행되면 될수록 GC 실행될 것들이 많아지게 되고, 결국에는 메모리 정리를 위해 쓰레드가 잠시 멈출 수도 있다... -> 비효율!

 

반면 비트 마스킹은 int 하나로 상태 관리하고, 추가/삭제 등의 연산이 필요 없기에 메모리에 영향 주지도 않는다!!

 

 

수정한 코드)

import java.io.*;

public class Main {

    static int r, c, max = 0;
    static char[][] map;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void dfs(int x, int y, int depth, int visited) {
        max = Math.max(max, depth);

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

            if (nx >= 0 && ny >= 0 && nx < r && ny < c) {
                int ch = map[nx][ny] - 'A';
                if ((visited & (1 << ch)) == 0) {  // 방문하지 않은 알파벳이면
                    dfs(nx, ny, depth + 1, visited | (1 << ch));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] rc = br.readLine().split(" ");
        r = Integer.parseInt(rc[0]);
        c = Integer.parseInt(rc[1]);

        map = new char[r][c];
        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = line.charAt(j);
            }
        }

        int firstCharBit = 1 << (map[0][0] - 'A');
        dfs(0, 0, 1, firstCharBit);

        System.out.println(max);
    }
}

 

비트 마스크 연산이 헷갈려서 GPT한테도 물어봤더니, 아래와 같은 답변을 줬다. 블로그에 나와있는 설명글보다 이 내용이 더 이해가 잘되어서 첨부함!

 

 

📌 전제: 알파벳을 비트로 관리하자!

• 알파벳 A ~ Z 는 26개 → 비트 26개로 관리 가능
• char - 'A' 를 하면 A는 0, B는 1, ..., Z는 25로 매핑됨
• int는 32비트니까 충분히 26개 알파벳 상태를 표현 가능!

---

🧩 예제 코드 해설

👇 코드 1

int visited = 0; // 아무 알파벳도 방문 안 함

• visited는 현재 방문한 알파벳을 나타내는 비트마스크입니다.
• 초기값 0은 모든 비트가 꺼져 있음 = 아무것도 방문 안 한 상태

visited = 00000000 00000000 00000000 00000000

---

👇 코드 2

visited |= (1 << 2);  // visited = 00000100

• 'C' - 'A' = 2 → C는 2번째 알파벳 (비트 위치 2번)
• 1 << 2 는 아래와 같이 2번째 비트만 켜진 값을 만듭니다:

1 = 00000000 00000000 00000000 00000001
1 << 2 = 00000000 00000000 00000000 00000100

• visited |= (1 << 2) 는 visited의 2번째 비트를 켜는 연산입니다:

기존 visited: 00000000 00000000 00000000 00000000
(1 << 2)     : 00000000 00000000 00000000 00000100
-----------------------------------------------
결과 visited : 00000000 00000000 00000000 00000100  ✅

이제 visited는 "C"가 방문된 상태를 나타내요.

---

👇 코드 3

if ((visited & (1 << 2)) != 0)

• 이건 2번 비트가 켜져 있는지 확인하는 조건입니다.
• & 연산은 둘 다 1일 때만 1이 되는 논리곱이므로:

visited     : 00000000 00000000 00000000 00000100
(1 << 2)    : 00000000 00000000 00000000 00000100
& 결과     : 00000000 00000000 00000000 00000100 → 0이 아님

따라서 "C"는 이미 방문한 상태가 됩니다.

---

👇 코드 4

visited &= ~(1 << 2); // visited = 00000000

이건 "C" 방문 해제, 즉 2번 비트를 끄는 연산입니다.

 

먼저 (1 << 2)로 2번 비트가 켜진 값을 만들고:

(1 << 2)  = 00000000 00000000 00000000 00000100

 

~(비트 NOT)를 하면:

~(1 << 2) = 11111111 11111111 11111111 11111011

 

그걸 &=로 적용하면:

visited    : 00000000 00000000 00000000 00000100
~(1<<2)    : 11111111 11111111 11111111 11111011
-----------------------------------------------
결과       : 00000000 00000000 00000000 00000000

 

이렇게 해서 "C"는 다시 방문 안 한 상태로 되돌아갑니다.

---

🎯 요약 정리

동작 코드 의미

 

방문 표시	`visited	= (1 << ch)`
방문 확인	(visited & (1 << ch)) != 0	ch번째 비트가 켜져 있는지 확인
방문 해제	visited &= ~(1 << ch)	ch번째 비트를 끈다

---

🧠 기억 팁!

• |= → 켜기
• & → 확인
• &= ~ → 끄기
• 1 << ch → ch번째 비트를 "1"로 만든다.