[백준 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

풀이 설명

1. (0,0)인덱스에서 시작해 상,하,좌,우 방향을 탐색하여 이동 가능한 칸을 대상으로 재귀를 쓰면 된다.

2. 매개변수로 받은 행,열 인덱스의 상하좌우를 조사하는 메소드 check를 선언한다.

   한 칸씩 움직일 때마다 해당 칸의 알파벳을 저장할 문자열 temp와,

   이동 횟수를 저장하는 cnt 변수도 매개변수로 넘겨준다.

3. check 메소드 내에서는 상 하 좌 우를 체크한다.

  3-1. 위로 이동이 가능하다면 그 칸의 인덱스와, 알파벳을 더한 temp, 현재 cnt + 1을 매개변수로 하여 check함수를            재귀호출한다.

  3-2. 아래 왼쪽 오른쪽 모두 같은 방법으로 check함수를 재귀호출한다.

  3-3. 위 조건을 모두 만족하지 않는다면, 더 이상 이동할 수 없으므로 현재까지의 이동횟수 cnt와 minVal을 비교하여            더 작은 값을 minVal로 갱신한다.

Java 코드

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

public class Main {
	
	static int R;
	static int C;
	static String[][] map;
	static int maxVal;

	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 String[R][C];
		for(int i=0; i<R; i++)
			map[i] = br.readLine().split("");
		
		String temp = map[0][0];
		check(0, 0, temp, 1);
		System.out.println(maxVal);
	}

	private static void check(int x, int y, String temp, int cnt) {
		if(x > 0 && !temp.contains(map[x-1][y])) //상
			check(x-1, y, temp + map[x-1][y], cnt+1);
		if(x < R-1 && !temp.contains(map[x+1][y])) //하
			check(x+1, y, temp + map[x+1][y], cnt+1);
		if(y > 0 && !temp.contains(map[x][y-1])) //좌
			check(x, y-1, temp + map[x][y-1], cnt+1);
		if(y < C-1 && !temp.contains(map[x][y+1])) //우
			check(x, y+1, temp + map[x][y+1], cnt+1);
		else {
			if(maxVal < cnt)
				maxVal = cnt;
		}
	}
}