백준 1987번: 알파벳

문제 설명

• 말이 가장 길게 움직일 수 있는 경우의 수를 구하는 문제입니다.

접근법

• 길을 탐색해보고 해당 길이 틀렸으면 다시 되돌아와 새로운 길을 가는 백트래킹을 활용할 수 있습니다.
• 알파벳 길이만큼의 배열을 활용해 중복되는 순간을 체크합니다.

정답

package simple_test;

import java.util.*;

public class Main {
	static int r;
	static int c;
	static char[][] board;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static boolean[] v;
	static int max;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringTokenizer st = new StringTokenizer(sc.nextLine(), " ");
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		v = new boolean[26];
		board = new char[r][c];
		for (int i = 0; i < r; i++) {
			board[i] = sc.nextLine().toCharArray();
		}

		BackT(0, 0, 0);
		System.out.println(max);
	}

	public static void BackT(int x, int y, int cnt) {

		if (v[board[x][y] - 'A']) {
			max = Math.max(max, cnt);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < r && 0 <= ny && ny < c) {
				v[board[x][y] - 'A'] = true;
				BackT(nx, ny, ++cnt);
				v[board[x][y] - 'A'] = false;
				--cnt;
			}

		}
	}
}