[DFS/BFS] 1987. 알파벳

[BOJ] 1987. 알파벳

📌 풀이 과정

모든 가능한 경로를 탐색한 뒤 그 중 가장 길이가 긴 것을 선택하는 것이기 때문에 DFS를 사용했다.

1. (0,0)에서 출발해 상하좌우로 이동한다.
   이때, 보드의 범위를 벗어나거나 이미 방문한 알파벳인 경우는 건너뛴다.

2. 이동이 가능하고 방문하지 않은 알파벳이라면, 해당 알파벳을 방문 처리하고 dfs를 재귀적으로 호출한다.
   cnt를 이용해 지나온 칸의 수를 세며, 이를 최대 값 maxCnt로 갱신한다.

3. 재귀 호출 후에는 방문 상태를 false로 돌려 다른 경로에서도 해당 알파벳을 다시 사용할 수 있게 한다.

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 알파벳_1987 {

	static int R, C, maxCnt = 0;
	static char[][] map;
	static boolean[] alphabet = new boolean[26];
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		R = Integer.parseInt(input[0]); // 세로
		C = Integer.parseInt(input[1]); // 가로
		
		map = new char[R][C];
		for(int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
		}
		
		alphabet[map[0][0] - 'A'] = true;
		dfs(0, 0, 1);

		System.out.println(maxCnt);
	}
	
	private static void dfs(int x, int y, int cnt) {
		maxCnt = Math.max(maxCnt, cnt); // 최대 칸 수 갱신
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
			if(alphabet[map[nx][ny] - 'A']) continue; // 이미 방문한 알파벳은 무시
			
			alphabet[map[nx][ny] - 'A'] = true;
			dfs(nx, ny, cnt + 1);
			alphabet[map[nx][ny] - 'A'] = false; // 백트래킹
		}
	}

}