[Java] 백준 / 알파벳 / 1987번

[Java] 백준 / 알파벳 / 1987번

문제

알파벳 문제 링크

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

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

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

입력

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

3 6
HFDFFB
AJHGDH
DGAGEH

출력

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

6

접근 방식

dfs를 통해 1행 1열부터 4방향으로 탐색을 하며 지나온 알파벳이 아닌 알파벳으로 이동한 가장 큰 거리를 구한다
추가로 백트래킹 조건으로 다른 경로로 같은 알파벳을 가진 노드를 제외시킨다
ex )
a b
b c

위 표에서 기억자와 니은자로 c에 도착하게 되고 이는 길이가 같기 때문에 하나를 제외시켜도 된다

방법 : 비트마스킹으로 알파벳을 방문한 것을 정수형으로 관리하고 이 정수를 2차원 노드 방문 배열에 저장하여, 또 다시 해당 노드에 방문했을 시 비트마스킹한 정수와 같다면 이는 다른 경로로 같은 알파벳을 통과해온것이 된다.

코드

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

public class Main_1987_정현명 {

	static int R,C;
	static int cntMax;
	static char matrix[][];
	static int visited[][];
	static int deltas[][] = {{-1,0},{0,1},{1,0},{0,-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());
		
		matrix = new char[R][C];
		
		for(int i=0;i<R;i++) {
			matrix[i] = br.readLine().toCharArray();
		}
		
		cntMax = 1;
		visited = new int[R][C];
		dfs_backtrack(0,0,1,1<<matrix[0][0]-'A' );
		System.out.println(cntMax);
	}
	
	
	// 2차원배열의 visited에 방문했을 때의 flag를 저장하여 다른경로로 같은 알파벳을 지나온 경우를 제외한다
	public static void dfs_backtrack(int i, int j, int cnt, int flag) {
		if(visited[i][j] == flag) return; // 다른 경로로 같은 알파벳을 지나왔을 때
		visited[i][j] = flag;
		cntMax = cntMax > cnt ? cntMax : cnt;
		for(int deltaIdx = 0; deltaIdx<4; deltaIdx++) {
			int nextI = i + deltas[deltaIdx][0];
			int nextJ = j + deltas[deltaIdx][1];
			if(nextI < 0 || nextI >= R || nextJ < 0 || nextJ >= C ) continue;
			if((flag & 1<<matrix[nextI][nextJ]-'A') == 0) dfs_backtrack(nextI,nextJ,cnt+1,flag | 1<<matrix[nextI][nextJ] -'A');
		}
	}

}