백준 - 1987 ( dfs, backtracking, bitmask )

 

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

1987번: 알파벳

 

(0,0) 부터 중복을 체크하면서 탐색하는 전형적인 탐색문제다.

나는 DFS로 접근해서 풀이하였다.

 

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

public class Main {

    static int[][] map;
    static int r,c;
    static boolean[] visited;
    static int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    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());
        visited = new boolean[26];
        map = new int[r][c];

        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = row.charAt(j) - 'A';
            }
        }

        System.out.println(dfs(0,0));
    }

    private static int dfs(int row, int col) {
        int count = 0;
        visited[map[row][col]] = true;

        for (int[] dir : dirs) {
            int x = row + dir[0];
            int y = col + dir[1];

            if (x < 0 || y < 0 || x >= r || y >= c || visited[map[x][y]]) {
                continue;
            }

            count = Math.max(count, dfs(x, y));
            visited[map[x][y]] = false;
        }

        return count + 1;
    }

}

 

하지만 성능이 결코 좋지 못했다.

DFS

그래서 성능을 올리기 위해 bit mask를 적용해보기로 했다.

 

bit mask란?

일반적으로 true/false 체크를 위해 boolean[] 을 사용할 수 있지만, 이는 결국 메모리와 배열 탐색 시간이 든다.

그것을 bit로 표현해서 성능을 올리는 기법이다.

이 문제에서 체크해야될 개수는 알파벳 개수인 26개인데 java int 자료형 기준으로 2^30 까지 표현이 가능하기 때문에 적합해 보인다.

1 << 30  =  1073741824
1 << 31  =  -2147483648     // int overflow

그럼 이제 알파벳을 저장할 0~25까지의 인덱스를 2의 제곱수로 1이 1개인 이진수로 변환하고

or 연산을 하면서 더해주고 and 연산으로 checking 하면 된다.

 

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

public class Main {

    static int[][] map;
    static int r,c;
    static int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    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 int[r][c];

        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = row.charAt(j) - 'A';
            }
        }

        System.out.println(dfs(0, 0, 0));
    }

    private static int dfs(int row, int col, int bits) {
        int count = 0;
        bits |= 1 << map[row][col];

        for (int[] dir : dirs) {
            int x = row + dir[0];
            int y = col + dir[1];

            if (x < 0 || y < 0 || x >= r || y >= c || ((1 << map[x][y]) & bits) != 0 ) {
                continue;
            }

            count = Math.max(count, dfs(x, y, bits));
        }

        return count + 1;
    }

}

 

- 새로 탐색한 비트 와 기존의 비트를 & (AND) 하면 겹치는 비트를 색출할 수 있다.

- 겹치지 않는다면 | (OR) 연산으로 현재 비트를 추가한다.

bit mask

- 시간이 많이 줄었지만,, 그래도 여전히 성능이 좋지 않다..

 

hint

- 문득, 문제 힌트를 보고 backtracking을 발견했다.

- 지금 내 알고리즘은 모~든 경우를 탐색하기 때문에 루트는 다르지만 탐색결과가 같은 길이 많이 존재한다.

ABC
BCD

예를들어 이런 경우 D로 가는 방법이 3개 존재하는데 어디로 가던 D에서는 같은 BIT(111)를 갖게된다.

D이후에 다른 경로들이 있다면, 결과가 같은 탐색을 적어도 3회는 하게될 것이다.

그러므로 visited 배열을 만들어서 체킹해주면 backtracking을 적용할 수 있을 것 같다.

 

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

public class Main {

    static int[][] map;
    static int r,c;
    static int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static int[][] visited;

    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 int[r][c];
        visited = new int[r][c];

        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = row.charAt(j) - 'A';
            }
        }

        System.out.println(dfs(0, 0, 0));
    }

    private static int dfs(int row, int col, int bits) {
        bits |= 1 << map[row][col];
        
        if (visited[row][col] == bits) {
            return 0;
        }
        visited[row][col] = bits;
        int count = 0;

        for (int[] dir : dirs) {
            int x = row + dir[0];
            int y = col + dir[1];

            if (x < 0 || y < 0 || x >= r || y >= c || ((1 << map[x][y]) & bits) != 0 ) { // and 시 겹치는 부분이 있는가?
                continue;
            }

            count = Math.max(count, dfs(x, y, bits));
        }

        return count + 1;
    }

}

visited

- 이제 좀 정상적인 시간이 나온다..

 

- 실무에서 과연 비트마스킹을 쓸 일이 있을진 모르겠지만.. 성능적으로 깨알같은 테크닉인 것 같다.