알파벳-1987번(Java)

https://www.acmicpc.net/problem/1987

1987번: 알파벳

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2 4

CAAB

ADCB

예제 출력 1 복사

3

예제 입력 2 복사

3 6

HFDFFB

AJHGDH

DGAGEH

예제 출력 2 복사

6

예제 입력 3 복사

5 5

IEFCJ

FHFKC

FFALF

HFGCF

HMCHH

예제 출력 3 복사

10

package a0819;

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

public class Main_bj_1987_알파벳_서울_12반_이서영 {
	
	static int r,c;
	static char[][] arr;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static int max =0;
	static int cnt =0;
	static HashMap<Character, Boolean>hm;
	
	public static boolean cango(int x, int y) {
		return x>=0 && x<r && y>=0 && y<c;
	}
	
	public static void find(int x, int y) {
		
		boolean toggle = false;
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(cango(nx,ny) &&  !hm.containsKey(arr[nx][ny])) { //알파벳 방문 여부를 hashmap에 저장
				toggle =true;
				cnt++;
				hm.put(arr[nx][ny],true);
				
				find(nx,ny);
				cnt--;
				hm.remove(arr[nx][ny]);
			}
		}
		if(toggle ==false) {
			max = Math.max(max,cnt );
		}
		
		
	}
	
	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());
		arr = new char[r][c];
		
		for(int i=0; i<r; i++) {
			String str = br.readLine();
			for(int j=0; j<c; j++) {
				arr[i][j] = str.charAt(j);
			}
		}
		hm = new HashMap<>();
		hm.put(arr[0][0], true);
		cnt=1;
		find(0,0);
		System.out.println(max);
	}
	
	
}