1987번 : 알파벳 [Java]

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

1987번: 알파벳

해결 방안

백트래킹을 사용한다. 알파벳 사용 여부를 확인하기 위한 배열을 하나 만들어 같은 알파벳을 두 번 지날 수 없도록 체크한다. 현재 위치를 알기 위한 i, j에다가 최대 칸수를 위한 cnt도 같이 가지고 다니는 게 따로 변수를 빼놓는 것보다 편한 것 같아 그렇게 처리하였다.

 

전체 코드

import java.util.Scanner;

public class Main {
	static int R, C;
	static char[][] map;
	static int ans = 0;
	static boolean[] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		map = new char[R][C];
		for (int i = 0; i < R; i++) {
			String s = sc.next();
			for (int j = 0; j < C; j++) {
				map[i][j] = s.charAt(j);
			}
		}

		visited = new boolean[26];
		visited[map[0][0] - 65] = true;

		dfs(0, 0, 1);
		System.out.println(ans);
	}

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	private static void dfs(int i, int j, int cnt) {

		for (int d = 0; d < 4; d++) {

			int nr = i + dr[d];
			int nc = j + dc[d];
			if (isIn(nr, nc) && !visited[map[nr][nc] - 65]) {
				visited[map[nr][nc] - 65] = true;
				dfs(nr, nc, cnt + 1);
				visited[map[nr][nc] - 65] = false;
			}
		}

		ans = Math.max(ans, cnt);

	}

	private static boolean isIn(int nr, int nc) {
		if (nr < 0 || nc < 0 || nr >= R || nc >= C)
			return false;
		else
			return true;
	}
}