백준 - 1987번: 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

풀이

이 문제는 그래프 탐색과, 백트래킹 기법을 사용해서 풀 수 있는 문제이다. 먼저 입력으로 주어지는 값들은 단순하다. 세로의 길이 R, 가로의 길이 C 그리고 각 칸의 대응되는 대문자 알파벳이다. 이제 말을 움직여서 말이 최대한 몇 칸을 지날 수 있는지만 구하면 된다.

문제를 풀기전 주요한 조건들을 파악해보면 우선 말은 좌측 상단 (1행 1열)에 놓여 있고 상하좌우로 움직일 수 있다 그리고 지금까지 나왔던 알파벳을 제외한 칸에는 갈 수 있다. 추가적으로 칸을 카운팅할 때 좌측 상단 칸도 포함한 상태에서 카운팅을 시작하게 된다. 이를 바탕으로 코드를 작성할 순서를 나열해보면

1. 문제에 필요한 입력정보들을 저장한다.
2. 좌측 상단을 가장 처음 방문하니, 해당 부분에 방문했다는 기록을 남긴다.
3. 이후 dfs 탐색을 실시한다.
4. 상하좌우 탐색을 진행하면서, 방문할 칸에 알파벳이 지금까지 나왔던 알파벳인지를 판단한다.
5. 만약 나왔던 알파벳이 아니라면 dfs 탐색을 재귀적으로 실시한다.

소스 코드

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

public class Main {

	static int R, C, max;
	static int dx[];
	static int dy[];
	static int alphabet[];
	static char board[][];

	public static void main(String[] args) throws Exception{
		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];
		alphabet = new int[26];
		dx = new int[]{1, 0, -1, 0};
		dy = new int[]{0, 1, 0, -1};

		for (int i = 0; i < R; i++) {
			char[] charArray = br.readLine().toCharArray();
			for (int j = 0; j < charArray.length; j++) {
				board[i][j] = charArray[j];
			}
		}

		alphabet[board[0][0] - 65] = 1;
		dfs(0, 0, 1);

		System.out.println(max);
	}

	private static void dfs(int x, int y, int count) {
		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 || alphabet[board[nx][ny] - 65] == 1) {
				continue;
			}

			alphabet[board[nx][ny] - 65] = 1;
			dfs(nx, ny, count + 1);
			alphabet[board[nx][ny] - 65] = 0;
		}

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