[백준] 1987번 : 알파벳

 

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

1987번: 알파벳

 

문제

 

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

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

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

 

입력

 

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

 

출력

 

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

 

 

풀이 방법

 

알파벳 개수만큼의 배열을 통해 값이 존재하면 true를, 그렇지 않으면 false로 설정한다.

이를 통해 지금까지 지나온 칸인지 아닌지를 판별할 수 있으며 판별시에는 인덱스를 통해 상하좌우를

검사해주어야 한다. 처음에는 BFS()를 이용하여 풀이를 하려고 하였으나 상하좌우에 인접한 인덱스가 동시에 입력이 되어야 하므로 방문여부를 체크하기가 까다로워 DFS를 이용하였다.

 

작성 코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

package baekjoon.graphTraversal;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BJ_1987 {       static int R,C;     static char arr[][];     static int D[][]={{-1,0},{1,0},{0,-1},{0,1}};     static int result[][];     static boolean alpha[];     static int max=Integer.MIN_VALUE;       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());         arr=new char[R][C];         result=new int[R*C][R*C];         alpha=new boolean[26];           for(int i=0;i<R;i++){             String s=br.readLine();             for(int j=0;j<s.length();j++){                 arr[i][j]=s.charAt(j);             }         }           DFS(0,0);           max++;         System.out.println(max);     }         public static void DFS(int x, int y){           alpha[arr[x][y]-65]=true;           for(int i=0;i<4;i++){             int ax=x+D[i][0];             int ay=y+D[i][1];               if(ax>=0 && ay>=0 && ax<R && ay<C){                   if(alpha[arr[ax][ay]-65]==false){                     result[ax][ay]=result[x][y]+1;                     DFS(ax,ay);                 }                 max=Math.max(max,result[ax][ay]);             }         }           alpha[arr[x][y]-65]=false;     } }