문제

이해

알파벳이 적혀있는 RxC 크기의 보드가 있다.

1행1열부터 시작하여 말을 이동하려 한다.

말은 상하좌우로만 이동할 수 있지만 새로 이동한 칸의 알파벳은 이전에 밟은 적 없는 알파벳이어야 한다.

최대로 밟을 수 있는 칸 수를 구하여라.

접근

쉬운 백트래킹 문제이다.

특정한 칸에서 움직일 수 있는 경우는 상하좌우이고 이를 말의 이동 규칙에만 유의하여 수행하면 된다.

이전에 밟은 문자는 새로 밟을 수 없기 때문에 이전에 밟은 문자를 기록할 boolean[26]의 변수가 필요하다.

모든 백트래킹 탐색이 끝나면 결과로 나온 최댓값을 출력하면 된다.

코드

package java_baekjoon;

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

public class prob1987 {
	static class xy {
		int x;
		int y;

		public xy(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static int R;
	static int C;
	static char[][] board;
	static int[] d_row = { -1, 0, 1, 0 };
	static int[] d_col = { 0, 1, 0, -1 };
	static boolean[] alpha_visited;
	static int ans = 0;

	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 + 1][C + 1];
		alpha_visited = new boolean[26];
		for (int i = 1; i <= R; i++) {
			String input = br.readLine();
			for (int j = 0; j < C; j++) {
				board[i][j + 1] = input.charAt(j);
			}
		}

		alpha_visited[board[1][1] - 'A'] = true;
		dfs(new xy(1, 1), 1);

		System.out.println(ans);
	}

	static void dfs(xy cdnt, int depth) {
		for (int i = 0; i < 4; i++) {
			int new_x = cdnt.x + d_row[i];
			int new_y = cdnt.y + d_col[i];

			if (new_x <= 0 || new_x > R || new_y <= 0 || new_y > C) {
				continue;
			}

			if(alpha_visited[board[new_x][new_y] - 'A']) {
				continue;
			}
			
			alpha_visited[board[new_x][new_y] - 'A'] = true;
			dfs(new xy(new_x, new_y), depth + 1);
			alpha_visited[board[new_x][new_y] - 'A'] = false;
		}
		ans = Math.max(ans, depth);
	}

}

결과

if문 조건에 오타가 생겨서 계속 오답이 발생했다..