백준 1987, 알파벳 - DFS, Backtracking

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

1. 아이디어

시작 지점 [0, 0] 에서부터 DFS 시작

• 다음 지점의 알파벳을 아직 방문 안한 경우, 탐색 확장
• 탐색 확장하면서 이동 가능한 칸 최대 개수 갱신 (DFS 함수 파라미터로 전달)
• 재귀 종료 조건: 다음 지점의 알파벳을 이미 방문한 경우 (이동 가능한 칸이 없는 경우)

---

DFS + Backtracking 으로 이동 가능한 최대 칸 수를 구함
=> 이동 가능한 최대 칸 수를 알아내기 위해서는, 가능한 모든 경로를 확인해야 함

• DFS 로 이동 가능한 경로를 탐색
• Backtracking 으로 가능한 모든 경로를 확인

2. 자료구조

• boolean[]: 알파벳 방문 확인
  => 길이 26 (알파벳 A ~ Z 개수)
  e.g. 알파벳 'B' 방문 확인 => check['B' - 'A']

3. 시간 복잡도

코드

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

public class Main {
	static int r, c;			// 입력 행, 열 개수
	static char[][] board;			// 알파벳이 적힌 row행 col열 보드
	static int maxNum = 0;			// 출력 값, 이동 가능한 최대 칸 수

	static boolean[] check = new boolean[26];	// 알파벳 방문 확인 (A ~ Z 26개)
	static int[] dy = { -1, 1, 0, 0 };		// 상하좌우
	static int[] dx = { 0, 0, -1, 1 };

	/* count: 이동한 칸의 수 (지나온 알파벳 개수) */
	static void dfs(int row, int col, int count) {
		// 현재 지점 기준, 상하좌우 확인
		for (int i = 0; i < 4; i++) {
			int nextRow = row + dy[i];
			int nextCol = col + dx[i];

			if (0 <= nextRow && nextRow < r &&
            		    0 <= nextCol && nextCol < c) {
				char nextAlpha = board[nextRow][nextCol];	// 다음 지점의 알파벳
				if (!check[nextAlpha - 'A']) {
					check[nextAlpha - 'A'] = true;
					dfs(nextRow, nextCol, count + 1);

					// 재귀 호출 복귀 시점: 방문 확인 배열 복구 => Backtracking
					check[nextAlpha - 'A'] = false;
				}
			}
		}

		maxNum = Math.max(maxNum, count);
	}

	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());
		board = new char[r][c];
		for (int i = 0; i < r; i++) {
			String str = br.readLine();
			for (int j = 0; j < c; j++)
				board[i][j] = str.charAt(j);
		}

		// [0, 0] 방문 처리하고 시작
		char start = board[0][0];
		check[start - 'A'] = true;
		dfs(0, 0, 1);

		System.out.println(maxNum);
	}
}