[BAEKJOON 백준] 1987 알파벳

www.acmicpc.net/problem/1987

1987번: 알파벳

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

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

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

 

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

 

DFS를 이용해서 문제를 풀었다.

 

먼저 입력값들을 받아주고, 시작점을 1,1로 해준다.

 

그리고 visit 배열을 만들어서 방문체크를 해준다.

 

그리고 4방탐색을 해서 주의에 다른 알파벳이 있다면 해당 위치를 불러줘서 또다시 확인을 하게된다.

 

그렇게 만들어진 cnt와 result를 비교를 통해 결과값을 출력해 준다.

 

 

 

 

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

public class Main {


	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static int R,C;

	static char arr[][];
	static boolean visit[];
	static int result=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());
		visit = new boolean[26];
		arr= new char[R + 1][C + 1];

		for (int i = 1; i <= R; i++) {
			String s = br.readLine();
			for(int j=1;j<= C;j++) {
				arr[i][j] = s.charAt(j-1);
				
			}
		}
		find(1,1,1);
		System.out.println(result);

	}
	private static void find(int i, int j,int cnt) {
		// TODO Auto-generated method stub
		visit[arr[i][j] - 'A'] = true;
		for (int k = 0; k < 4; k++) {
			int x = i + dx[k];
			int y = j + dy[k];
			if (x > 0 && x <= R && y > 0 && y <= C) {
				
				if(!visit[arr[x][y] - 'A']) {
					find(x,y,cnt+1);
				}
			}
		}
		visit[arr[i][j] - 'A'] = false;
		result=Math.max(cnt, result);
		
	}

}