백준 1987 알파벳 (JAVA 자바)

 

문제 출처 - https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

문제

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

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

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

입력

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

출력

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

 

문제 유형

DFS

 

 

코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int map[][];
	static boolean alpha[], visited[][];
	static int R, C;
	static int res;
	
	static int dr[] = {-1, 1, 0, 0};
	static int dc[] = {0, 0, -1, 1};
	
	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());
		
		map = new int [R][C];
		alpha = new boolean [26];
		visited = new boolean [R][C];
		res = -1;
		
		for (int r = 0; r < R; r++) {
			st = new StringTokenizer(br.readLine());
			String line = st.nextToken();
			
			for (int c = 0; c < C; c++) {
				map[r][c] = line.charAt(c) - 65;
			}
		}
		
		visited[0][0] = true;
		alpha[map[0][0]] = true;
		go(0, 0, 1);
		System.out.println(res);
	}
	
	static void go(int cr, int cc, int cnt) {
		for (int dir = 0; dir < 4; dir++) {
			if(cnt > res)
				res = cnt;
			
			int nr = cr + dr[dir];
			int nc = cc + dc[dir];
			
			if(nr < 0 || nc < 0 || nr >= R || nc >= C)
				continue;
			
			if(visited[nr][nc])
				continue;
			
			if(alpha[map[nr][nc]])
				continue;
			
			alpha[map[nr][nc]] = true;
			visited[nr][nc] = true;
			
			go(nr, nc, cnt + 1);
			
			alpha[map[nr][nc]] = false;
			visited[nr][nc] = false;
		}
	}
}

DFS 문제였고 인접한 상하좌우 칸을 방문하는데 이미 한번 방문한 적이 있는 알파벳 칸이라면 다시 방문하지 못한다는 조건이 있는 문제였다. 따라서 alpha 배열을 통해서 알파벳의 방문체크를 해주었다. map 배열은 char 형으로 관리해주어도 되지만 그냥 아스키코드 써서 -65하면 A라면 0, B라면 1 이렇게 될테니까 int 형으로 저장을 하였고 그 알파벳에서 -65를 뺸 것을 alpha 배열의 인덱스로 썼다. 처음에 1번 테케의 답이 5가 나와서 당황했는데 생각해보니까 처음에 시작하는 (1,1)칸도 방문체크와 알파벳 방문체크를 해주어야 하는 사실을 까먹었었다. 그래도 금방 찾아서 다행이었다. 재귀 타는 문제는 왜 긴장하게 되는지 모르겠다...