백준 1987번) 알파벳(JAVA)

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

1987번: 알파벳

 

 

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

 

# 풀이방법

간단한 BFS 문제이다. 처음 위치 = 좌측 상단에 값을 넣은 후,

백트래킹으로 여러 경로의 수를 추적하며, 지나간 길의 최대값을 갱신해주면 된다.

 

처음에 자신이 지나간 길인지 아닌지를 stack을 이용해서

코드를 작성했는데 시간 초과가 나버렸다... 

아무래도 stack에 알파벳을 넣다 뺐다하는 시간과 같은 알파벳이 있는지 확인하는 과정에서 많은 시간을 써버린 것 같다.

 

어떤 방법으로 자신이 지난 알파벳을 확인 할 수 있을까? 고민하다가 

스택이 아닌 문자열을 백트래킹에 매개값으로 놓은 후,

매개 값으로 들어온 문자열에 String 객체 contain 메소드로 값이 있는지 확인하는 과정을 통해

시간을 단축 시킬 수 있었다.

 

public static void backTrack(int i,int j,int max,String str) {
        
        for(int k=0; k<4; k++) {
            
            if(i+dy[k] < 0 || i+dy[k] >= R || j+dx[k] < 0 || j+dx[k] >= C)
                continue;
            //범위를 벗어났을경우,
            
            if(!str.contains(""+board[i+dy[k]][j+dx[k]])) {
                
                backTrack(i+dy[k],j+dx[k],max+1,str+board[i+dy[k]][j+dx[k]]);
            }
            //String의 contain메소드를 이용하여 이미 지나간 문자열이 있는지 확인해준다.
            
        }
        
        if(ans < max) {
            ans = max;
        }
        
    }

 

골4의 문제일지라도 bfs와 백트래킹 문제에 익숙한 사람이라면 누구나 쉽게 풀 수 있는 문제였다.

 

다른 분의 코드를 보니 알파벳의 총 개수 26이므로,

boolean[] visited = new boolean[26]을 선언해 방문처리 하는 과정을 참고하였다.

 

일일히 contain을 써서 같은 알파벳이 있는지 찾아가는 비효율적인 방식보다

알파벳이 26개라는 특성을 이용해 booelan[] 배열로 같은 알파벳 있는지 효율적으로 

탐색하는 방법도 있다는 것을 깨닫게 되었다.

 

조금만 생각해보면 동일한 ouput을 내기 위해 더 효율적으로 코드를 작성 할  수 있었는데 

좀 더 열심히 공부해야겠다.

 

# 전체코드

import java.util.*;
//2t
 
public class Main {
    
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,1,-1};
    
    static int R;
    static int C;
    static char[][] board;
    static int ans = 0;
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        R = sc.nextInt();
        C = sc.nextInt();
        
        board = new char[R][C];
        
        for(int i=0; i<R; i++) {
            board[i] = sc.next().toCharArray();
        }
        
        
        backTrack(0,0,0,""+board[0][0]);
        //처음 위치 맨왼쪽, 맨위쪽
        
        System.out.println(ans+1);
 
    }
    
    public static void backTrack(int i,int j,int max,String str) {
        
        for(int k=0; k<4; k++) {
            
            if(i+dy[k] < 0 || i+dy[k] >= R || j+dx[k] < 0 || j+dx[k] >= C)
                continue;
            //범위를 벗어났을경우,
            
            if(!str.contains(""+board[i+dy[k]][j+dx[k]])) {
                
                backTrack(i+dy[k],j+dx[k],max+1,str+board[i+dy[k]][j+dx[k]]);
            }
            //String의 contain메소드를 이용하여 이미 지나간 문자열이 있는지 확인해준다.
            
        }
        
        if(ans < max) {
            ans = max;
        }
        
    }
 
}