백준 1987 알파벳(Gold4)

정답코드

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

public class Main {
	
	static String alpha[][];
	static int R;
	static int C;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static String result = "";
	
	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());
		alpha = new String[R][C];
		
		for(int i = 0; i < R; i++) {
			String input = br.readLine();
			for(int j = 0; j < C; j++) {
				alpha[i][j] = Character.toString(input.charAt(j)) ;
			}	
		}

		String str = ""+alpha[0][0]; 
		boolean visited[][] = new boolean[R][C];
		DFS(0,str,visited,0,0);	
		
		System.out.println(result.length());
	}
	
	public static void DFS(int depth, String str,boolean[][] visit, int i, int j) {
		
		int x = i;
		int y = j; 
		
        //현재  알파벳 문자열 길이가 더 길면 업데이트 해준다
		if(str.length()>result.length())result = str;
		
        //동서남북에 대해서 DFS
		for(int n = 0; n < 4; n++) {
			int nx = x+dx[n];
			int ny = y+dy[n];

			//범위 넘으면 continue
			if(nx>=R||nx<0||ny>=C||ny<0)continue;
			
			//이미 방문했거나 완성 문자에 포함되어있으면 continue
			if(visit[nx][ny] == true || str.contains(alpha[nx][ny]) == true)continue;

			//아니라면 
			visit[nx][ny] = true;
			DFS(depth+1,str+alpha[nx][ny],visit,nx,ny);
			visit[nx][ny] = false;
			
		}
	}
}

전략

• 전략 이 전에 DFS 재귀돌릴 때 숫자로만 하지 말고 String으로 저장해가면서 return 조건 찾던게 생각이 나서 그걸 사용하기로 함

• (0,0)부터 시작해서 상하좌우로 이동하면서 이미 저장했던 알파벳이 아니거나 (str안에 없거나) 방문한 적이 없다면 str + 해서 다시 재귀로 돌려줌

• 재귀 시작점에서 현재 들어오는 str의 길이가 지금까지 저장되어있는 str의 최댓값보다 크다고 하면은 max_length를 업데이트