Backtracking 백준 알고리즘 자바 1987 ‘알파벳’ 문제풀이

Problem

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

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

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

Solution

처음에 List를 이용해 해당 문자를 지난 적이 있는지 contains로 확인했다. 성공했지만 속도가 꽤 느렸다. visit배열로 바꾸니 3분의 1이나 줄였다!

• 방향 배열 dx, dy를 만들고 for문을 돌며 각 방향을 모두 방문한다.
• 맵의 범위를 넘지 않기 위해 if(xx > 0 && yy > 0 && xx <= r && yy <= c) 다음 방문 위치의 범위를 항상 확인한다.
• 저장해야 하는 값이 위치값이 아니라 문자값이므로 visit[arr[x][y] - 'A'] 처럼 아스키코드 연산으로 값을 저장한다. 따라서 알파벳 개수 26만큼 배열을 생성한다.
• 몇 번 움직였는지 변수 d를 이용해 호출마다 값을 넘겨준다. 최대 값을 math.max로 구한뒤 max 를 출력한다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	static int r, c, max = 0;
	static char[][] arr;
	static boolean[] visit;
	
	private static void dfs(int x, int y, int d) {
		int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; // north, south, west, east
		
		visit[arr[x][y] - 'A'] = true;
		for(int i = 0; i < 4; i++) {
			int xx = x + dx[i], yy = y + dy[i];
			
			if(xx > 0 && yy > 0 && xx <= r && yy <= c) {
				if(!visit[arr[xx][yy] - 'A']) dfs(xx, yy, d + 1);
			}
		}
		visit[arr[x][y] - 'A'] = false;		
		max = Math.max(max, d);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = br.readLine().split("\\s");
		r = Integer.parseInt(tmp[0]); c = Integer.parseInt(tmp[1]);
		arr = new char[r+1][c+1]; visit = new boolean[26];
		
		for(int i = 1; i <= r; i++) {
			String str = br.readLine();
			for(int j = 1; j <= c; j++) arr[i][j] = str.charAt(j-1);
		}
		dfs(1, 1, 1); System.out.print(max);
	}
}