알고리즘 풀이 - 백준 1987(알파벳, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

RxC 크기의 보드의 각 위치에 대문자 알파벳이 하나씩 있고, 좌측 상단에 말이 있다면 상하좌우로 움직여 지금까지 지나오지 않은 알파벳으로만 이동 가능할 때, 최대 이동 가능한 칸 수를 구하는 문제

 

 

2. 풀이

 

① 완전 탐색 이용하기

이 방법은 굉장히 쉽다. 알파벳은 총 26개 이므로 26크기의 boolean 배열을 만들고 사용된 알파벳의 위치는 true로 바꾸어가며 탐색을 수행하면 된다.

재귀를 이용하여 각 위치를 탐색한 뒤 그 결과가 최대값이 되는 경우를 저장한 뒤 출력한다.

하지만 최대 20x20이기 때문에 모든 탐색을 수행하게 되면 시간이 매우 오래 걸린다. 따라서 아래와 같이 더 효율적인 방법 또한 찾아보았다.

 

② 백트래킹(비트마스크 이용)으로 풀기

비트를 이용하여 각 위치를 방문 시에 현재 비트값을 저장하면 그 비트값에는 지금까지 방문한 모든 알파벳이 저장된 상태일 것이다.

이를 이용하여 같은 비트값이 전달되는 경우, 동일한 과정이 반복되는 것을 막기 위해 재귀 함수에서 return하는 식으로 수행이 가능하다. 예를 들어서 아래 그림을 보자.

 

위 그림에서 최대의 이동 횟수는 무조건 A - B - C - D 이다. 그러면 이동 가능한 경로는 2가지가 있다.

아래와 같이 빨간색 / 파란색의 경로가 있다.

 

 

그럼, C의 위치를 방문했을 때, 비트마스크 값은 111로 저장될 것이다.(A, B, C 이므로) 이 때, 파란색으로 이동을 먼저 했다면 C에 111이 저장된 상태에서 D를 방문했을 것이다.

만약 완전 탐색을 ①과 같이 하였다면 파란색 탐색 이후, 빨간색도 D의 위치까지 모두 탐색하게 된다.

 

하지만 비트마스크의 경우 빨간색 방향으로 C를 방문했을 때, 이미 기존에 동일한 비트 값 111이 저장되어 있으므로 더 이상 추가 방문을 하지 않게 된다.

 

이 경우 백트래킹을 통해 불 필요한 탐색을 줄일 수 있기 때문에 전체 문제 해결 시간이 줄어들게 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① 완전 탐색으로 풀기

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

public class Main{
    static int R;
    static int C;
    static boolean[] alp = new boolean[26];
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    static char[][] board;
    static int ans = 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());

        // 주어진 알파벳 보드 저장
        board = new char[R][C];
        for(int i=0; i < R; i++){
            String s = br.readLine();
            for(int j=0; j < C; j++){
                board[i][j] = s.charAt(j);
                
                // (0, 0)의 알파벳은 이미 탐색 완료이므로 true로 저장
                if(i == 0 && j == 0){
                    alp[board[i][j] - 'A'] = true;
                }
            }
        }
        backtrack(0, 0, 1);
        System.out.println(ans);

        br.close();
    }

    private static void backtrack(int y, int x, int move){
        ans = Math.max(move, ans);

        // 4방향으로 움직이며 재귀 함수 지속 수행
        for(int i=0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            // 범위를 벗어나면 다음 반복문으로 넘어간다.
            if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
            
            // 다음 위치의 알파벳 저장
            char next = board[ny][nx];
            
            // 이미 사용된 알파벳이면 다시 반복문 수행
            if(alp[next-'A']) continue;

            // 현재 위치의 알파벳 true로 반환
            alp[next-'A'] = true;
            // 재귀 수행
            backtrack(ny, nx, move+1);
            
            // 재탐색이 가능하도록 false로 재전환
            alp[next-'A'] = false;
        }
    }
}

 

② 백트래킹(비트마스크 이용)으로 풀기

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

public class Main{
    static int R;
    static int C;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    static int[][] board;
    static int[][] visited;
    static int ans = 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());

        board = new int[R][C];
        visited = new int[R][C];
        for(int i=0; i < R; i++){
            char[] c = br.readLine().toCharArray();
            for(int j=0; j < C; j++){
                board[i][j] = c[j] - 'A';
            }
        }
        backtrack(0, 0, 1 << board[0][0], 1);
        System.out.println(ans);

        br.close();
    }

    private static void backtrack(int y, int x, int bit, int move){
        // 지금까지 이동한 경로와 동일하다면 추가 탐색 불 필요
        if(visited[y][x] == bit) return;
        
        // 현재 위치에 bit를 저장하여 현재까지 이동한 알파벳을 모두 저장
        visited[y][x] = bit;
        
        // 최대값을 갱신
        ans = Math.max(move, ans);
        for(int i=0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            // 범위를 벗어나면 추가 탐색
            if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
            
            // 현재 bit 값과 알파벳을 & 연산해서 0이 아니라면 이미 이전에 탐색된 알파벳
            // 따라서 반복문 재수행
            if((bit & 1<<board[ny][nx]) != 0) continue;
            
            // 다음 위치와 비트값 등을 전달
            backtrack(ny, nx, bit|1<<board[ny][nx], move+1);
        }
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.