[백준 Gold 5] 1987 알파벳 - Java

문제 링크 : www.acmicpc.net/problem/1987

1987번: 알파벳

 

접근 과정

• 시작점은 좌측 상단으로 고정,  이동방향은 상-하-좌-우.
• 이동방향이 상화좌우이기에, DP가 아닌 DFS로 접근
• 알파벳이 중복되지 않고 갈 수 있는 경로를 탐색
• 어떻게 지나온 길의 알파벳을 저장하고 비교할건지가 관건 (저장된 알파벳의 수 = 이동 칸의 수)
• HashSet -> boolean[] -> BitMask로 방식을 바꿔가며 시간을 줄여나감. 

 

소스 코드 및 결과

   Code 1 : HashSet<Character>

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

/* 
    알파벳 
    dfs (HashSet)
*/
public class BOJ1987 {

    static int max, R, C;
    static HashSet<Character> alphabet; // 사용한 알파벳을 저장
    static char[][] board; 
    static int[][] direction = {{-1,0}, {1,0},{0,-1},{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());

        board = new char[R][C];
        for(int i= 0; i<R; i++){
            board[i] = br.readLine().toCharArray();
        }

        max = 0;  // 최대 이동 칸의 수
        alphabet = new HashSet<>();
        alphabet.add(board[0][0]); // 시작 칸의 알파벳을 저장
        dfs(0, 0);

        System.out.println(max);
    }

    static void dfs(int r, int c){

        boolean possible = false;  // 다음 이동이 가능한지 체크

        for(int i = 0; i<4; i++){
            int nr = r+direction[i][0];
            int nc = c+direction[i][1];

            if (nr>=0 && nr<R && nc>=0 && nc<C) {  // 다음 이동 좌표가 볌위안에 존재하는지 
                if (alphabet.contains(board[nr][nc])) { // 다음 좌표의 알파벳을 이미 지나왔는지
                    continue;
                }
                possible = true; // 다음 이동 가능

                alphabet.add(board[nr][nc]); // 알파벳을 추가하고 DFS
                dfs(nr, nc);
                alphabet.remove(board[nr][nc]); // 추가한 알파벳 제거
            }
        }

        if (!possible) {  // 더 이상 이동이 불가한 경우, 이동 거리를 갱신
            max = Math.max(max, alphabet.size());
            return;
        }
    }
}

   결과:

   

   Code 2 : boolean[26]

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

/* 
    알파벳 
    dfs (boolean[])
*/
public class BOJ1987 {

    static int max, R, C;
    static char[][] board;
    static boolean[] visit;  // 사용한 알파벳을 boolean값으로 저장
    static int[][] direction = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 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());

        board = new char[R][C];
        for(int i= 0; i<R; i++){
            board[i] = br.readLine().toCharArray();
        }

        visit = new boolean[26];  // 알파벳의 수만큼 할당
        visit[board[0][0]-'A'] = true;  // 시작 칸의 알파벳을 체크

        max = 0;
       
        dfs(0, 0, 1); // 줄, 칸, 이동거리

        System.out.println(max);
    }

    static void dfs(int r, int c, int d){

        for(int i = 0; i<4; i++){
            int nr = r + direction[i][0];
            int nc = c + direction[i][1];

            if (nr>=0 && nr<R && nc>=0 && nc<C) {  // 다음 이동 칸이 범위 안에 있다면
                if (!visit[board[nr][nc]-'A']) { // 이미 사용된 알파벳이 아니라면
                    visit[board[nr][nc]-'A'] = true;
                    dfs(nr, nc, d+1); // 거리를 추가하고 dfs 진행
                    visit[board[nr][nc]-'A'] = false;
                }                
            }
        }
        max = Math.max(max, d); // 이동거리 갱신
    }
}

   결과:

   

   Code 3 : BitMast

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

/* 
    알파벳 
    dfs (비트마스크)
*/
public class BOJ1987 {

    static int max, R, C;
    static char[][] board;
    static int[][] visit; // 해당 칸에 도착할 때까지 사용한 알파벳을 비트(int)값으로 저장
    static int[][] direction = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 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());

        board = new char[R][C];
        for(int i= 0; i<R; i++){
            board[i] = br.readLine().toCharArray();
        }

        visit = new int[R][C];

        max = 0;
       
        dfs(0, 0,1<<board[0][0]-'A' ,1);  // 줄, 칸, 시작 칸의 알파벳을 비트값으로 저장하고 시작, 이동거리 

        System.out.println(max);
    }

    static void dfs(int r, int c, int check_bit, int d){

        if (visit[r][c] == check_bit) { // 조회하려는 비트값(이동경로)를 이미 조회했다면.
            return;
        }        

        visit[r][c] = check_bit; // 해당 칸의 이동경로(비트값) 갱신

        max = Math.max(max, d);  // 현재까지의 최대 이동거리 갱신

        for(int i = 0; i<4; i++){
            int nr = r + direction[i][0];
            int nc = c + direction[i][1];

            if (nr >= 0 && nr<R && nc>=0 && nc<C) { // 다음 이동 칸이 볌위내에 존재한다면
                if ((check_bit & 1<<board[nr][nc]-'A') == 0) { // 이미 사용된 알파벳이 아니라면
                    dfs(nr, nc,check_bit|1<<board[nr][nc]-'A', d+1); // 알파벳 비트를 추가하고 dfs 지속
                }
            }
        }        
    }
}

   결과:

 

 

P.S 비트마스크는 아직 익숙하지 않아 좀 더 학습이 필요함.