[BOJ] 1987 알파벳

1987번: 알파벳 (acmicpc.net)

이건 사실 백트래킹으로 풀려고 했는데, 잘 안되어서 기존에 하던대로 완전탐색으로 풀었다.
오늘 백트래킹을 처음 공부했는데 아직 감이 잘 안잡힌다.

HashMap을 이용해서 풀었다. hashmap에 모든 알파벳을 집어넣는 for문도 실행속도에 영향이 있어보인다. 사실 이부분은 배열로 풀어도 상관없다. 다만 배열의 인덱스를 계산해주기 귀찮아서 해쉬맵으로 풀었다.
그리고 스트링을 이용해서 방향을 표기해주었는데
“1210”.charAt(index) -‘1’ 이렇게 해서 0 +1 0 -1 을 배열대신 사용하였다.
이것도 속도에 긍정적인지는 잘 모르겠다.

nextpermutation도 공부해야하고, 백트래킹, 분할정복도 주말에 정리를 한번 해야겠다.

package com.algo.boj;

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

public class BOJ1987Alphabet {
	private static int R,C;
	private static HashMap<Character,Integer>  history;
	private static char[][] map;
	private static int max;
	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());
		map= new char[R][];
		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
		}
		history = new HashMap<>();
		for (char ch = 'A'; ch <= 'Z'; ++ch) 
			history.put(ch,0);
		history.put(map[0][0],1);
		//오른쪽 먼저탐색  -> 아래로 ->왼쪽 -> 
		dfs(0,0,1);
		System.out.print(max);
	}
	//0 은 오른쪽 1 은 아래 왼쪽 
	private static void dfs(int i, int j, int cnt) {
		max = max>cnt? max : cnt; 
		for (int d = 0; d < 4; d++) {
			//오른쪽 먼저탐색  -> 아래로 ->왼쪽 -> 
			int nr= i + "1210".charAt(d)-'1';
			int nc= j + "2101".charAt(d)-'1';
			if(nr<0 || nr>=R || nc<0|| nc>=C) continue;
			if(history.get(map[nr][nc])==1) continue;
			history.put(map[nr][nc], history.get(map[nr][nc])+1);
			dfs(nr, nc,cnt+1);
			history.put(map[nr][nc], history.get(map[nr][nc])-1);
		}
	}

}