[백준][1987]알파벳

 

 

/* 문제설명 */

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

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

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

입력

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

출력

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

 

 

 

---

 

 

 

/* 풀이방법 */

백트래킹을 활용해서 풀이했다.

이미 지나온 알파벳인가 아닌가 판별하기 위해 ArrayList를 썼다가 시간초과가 났다.

(+)컬렉션의 시간복잡도에 대해 공부해야겠다는 필요성을 느꼈다.

http://kwseo.github.io/2015/09/24/time-complexity-about-collections/

그래서 boolean배열을 하나 만들어 이미 접근한 알파벳인지 알아보는데 썼다.

이러한 형태인데, 0은 A, 1는 B . . . 25는 Z와 매칭된다.

false인 상태면 아직 해당 알파벳이 접근한 적이 없다는 뜻이고, true이면 해당 알파벳을 이미 지나왔다는 뜻이다.

 

시작점 (0, 0)으로부터 탐색할 수 있는 깊이 만큼 DFS를 사용해서 탐색하고, 맨끝 노드에 도달했다면

지금까지의 count를 max와 비교한다. 

그리고 해당 DFS를 빠져나오면 다음 노드를 탐색하기위해 방금 그 노드의 접근 기록을 지운다

방금 노드의 alpa를 다시 false로 만들고, count도 1 뺀다.

 

상하좌우 순으로 순회하므로 다음과 같은 Map에서 아래와 같은 상황이 노드 끝까지 순회한 상황이다.

더이상 순회 할 수 없으므로 count를 max와 비교하고 해당 노드를 빠져나온다.

(왼)해당 순회 끝 (오)백트래킹

그러면 다음과 같이 백트래킹 과정이 일어나게 된다. 해당 노드를 방문하기 전으로 돌리는 것이다.

 

 

 

 

---

 

/* 해답코드 */

package baekjoon;

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

public class b1987 {
	public static int[] dr = { -1, 1, 0,0};	//상하좌우
	public static int[] dc = { 0, 0, -1,1 };
	public static int R;
	public static int C;
	public static int max=0;
	public static int count=1;
	public static char[][] map;
	public static boolean[] alpa = new boolean[26];
	
	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 char[R][C];
		for (int r = 0; r < R; r++) {
			map[r] = br.readLine().toCharArray();
		}
		alpa[(int)map[0][0]-65]=true;
		dfs(0,0);
		System.out.println(max);
	}
	
	public static void dfs(int r, int c) {
		for(int d=0;d<4;d++) {
			int nr = r+dr[d];
			int nc = c+dc[d];
			if(nr>=0&&nr<R&&nc>=0&&nc<C&&!alpa[(int)map[nr][nc]-65]) {	
				alpa[(int)map[nr][nc]-65]=true;
				count++;
				dfs(nr,nc);	
				alpa[(int)map[nr][nc]-65]=false;
				count--;	
			}
			if(d==3) {
				if(max < count)
					max = count;			
			}
		}
	}
}