[JAVA] SWEA 7699 수지의 수지 맞는 여행 [BFS]

전체 코드

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

public class SWEA_7699_수지의수지맞는여행 {

	static int R, C, T, MAX;
	static boolean[] v;
	static int[] dy = { 1, -1, 0, 0 }; // 상,하,우,좌
	static int[] dx = { 0, 0, 1, -1 };
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		
		for (int test = 1; test <= T; test++) {
			MAX = -1;
			String[] tmp = br.readLine().split(" ");
			R = Integer.parseInt(tmp[0]);
			C = Integer.parseInt(tmp[1]);

			char[][] arr = new char[R][C];
			v = new boolean[26]; //알파벳 개수
			
			for (int i = 0; i < R; i++) {
				char[] chr = br.readLine().toCharArray();
				for (int j = 0; j < C; j++) {
					arr[i][j] = chr[j];
				}
			}
			v[arr[0][0] - 'A'] = true; // char형 문자에서 'A'를 빼 인덱스로 사용
			bfs(0, 0, 1, arr);
			
			System.out.println("#" + test + " " + MAX);

		}

	}

	private static void bfs(int y, int x, int cnt, char[][] arr) {
		if(cnt > MAX) //최대값 체크
			MAX = cnt;
		if(cnt == 26) //알파벳 개수이상 올라갈 수 없으므로
			return;
		
		for(int i=0; i<4; i++) { //사방 이동
			int ry = y + dy[i];
			int rx = x + dx[i];
			if(ry>=0 && ry<R && rx>=0 && rx<C) { // ry, rx가 배열 범위 내에 있다면
				int idx  = arr[ry][rx] - 'A'; //알파벳 인덱스
				if(!v[idx]) { // 해당 알파벳에 방문한적이 없다면
					v[idx] = true; // 트루 체크 후 
					bfs(ry, rx, cnt+1, arr); // 재귀
					v[idx] = false; // 위의 재귀들 모두 복귀 후 false로 변환 후 다음 재귀
				}
			}
		}
	}

}

 

문제 핵심 코드

private static void bfs(int y, int x, int cnt, char[][] arr) {
	if(cnt > MAX) //최대값 체크
		MAX = cnt;
	if(cnt == 26) //알파벳 개수이상 올라갈 수 없으므로
		return;
	
	for(int i=0; i<4; i++) { //사방 이동
		int ry = y + dy[i];
		int rx = x + dx[i];
		if(ry>=0 && ry<R && rx>=0 && rx<C) { // ry, rx가 배열 범위 내에 있다면
			int idx  = arr[ry][rx] - 'A'; //알파벳 인덱스
			if(!v[idx]) { // 해당 알파벳에 방문한적이 없다면
				v[idx] = true; // 트루 체크 후 
				bfs(ry, rx, cnt+1, arr); // 재귀
				v[idx] = false; // 위의 재귀들 모두 복귀 후 false로 변환 후 다음 재귀
			}
		}
	}
}

 

전형적인 DFS 문제였다.

 

처음에 BFS로 시도했었는데, 코드로만 봐도 너무 많은 횟수가 예상되었다.

그로 인해 BFS와 DFS의 풀이 기준을 생각해볼 수 있는 문제였다.

 

최단 경로쪽은 BFS , 최대(MAX) 관련 경로는 DFS라는 가닥을 잡았다.

물론 모든 문제에 무조건적으로 적용되는건 아니니 시작을 이 정도로 잡고 풀어나가면 좋겠다.