[백준] 1987. 알파벳 (골드4) - DFS

Kiefer Sol·2024년 8월 7일

목록 보기

15/35

1987. 알파벳 (골드4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	127991	38662	23499	28.099%

문제

세로 $R$ 칸, 가로 $C$ 칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ( $1$ 행 $1$ 열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

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

출력

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

예제 입력 1
2 4
CAAB
ADCB

예제 출력 1
3

예제 입력 2
3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2
6

풀이

알파벳을 Char형태로 바꿔 해당 수를 인덱스로 하는 방문배열 생성
DFS생성
2.1. 사용된 알파벳이 나오면 return -> 더 이상 가지가 내려가지 않는다.
2.2. 사용된 알파벳이 나오지 않고 계속 진행
```
2.2.1. 체크배열 true로 변경, 카운트 증가, 최대 갯수 카운트
2.2,2. 사방 돌면서 DFS 진행시키기
2.2.3. 체크 배열 돌기
```

public class Search_1987 {
	public static int R,C;
	public static int[][] arr;
	public static boolean[] isVisited;
	public static int ans;
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {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()); 
		
		arr = new int[R][C];
		isVisited = new boolean[26]; // 알파벳의 갯수
		ans = 0;
		
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for(int j=0; j<C; j++) {
				arr[i][j] = str.charAt(j)-'A'; // 해당 문자열을 char문자 형태로 바꿔 그에 따른 인덱스 사용하기
			}
		}
		DFS(0,0,0);
		System.out.println(ans);
	}
	
	public static void DFS(int x, int y, int count) {
		if(isVisited[arr[x][y]]) { //사용된 알파벳이 나오면 더 이상 진행 x
			return; // return을 안해주면 밑까지 계속 내려가서 진행되서 리소스 낭비
		}else {
			isVisited[arr[x][y]]=true; // 사용체크
			count++; // 사용 알파벳 갯수 증가
			ans = Math.max(ans, count); // 각 가지마다 최대 사용 갯수 확인
			
			for(int i =0;i<4; i++) { // 칸 이동
				int xx = x + dx[i];
				int yy = y + dy[i];
				
				if(xx<0 || xx>=R || yy<0 || yy>=C ) continue;
				DFS(xx,yy,count);
			}
			isVisited[arr[x][y]]=false; // 현재 알파벳 사용 안함으로 풀어주기
			
		}
		
	}
}