[Java] SWEA 7699.수지의 수지맞는 여행 D4

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqUzj0arpkDFARG 

SW Expert Academy

 

문제 자체는 기본적인 DFS 백트래킹을 사용해서 풀 수 있는 문제입니다.

하지만 가지치기에 따라 실행시간이 큰 차이를 보였습니다.

생각해보면 문제에서 주어진 테스트케이스의 조건에서, R과 C의 크기가 1 이상 20 이하입니다.

즉 최대 400칸의 맵이 주어지는 건데 알파벳의 개수는 26개로 제한되어있기 때문에 가지치기를 통해 자르지 않는 경우 생각보다 훨씬 더 많은 추가 탐색이 실행될 걸 알 수 있습니다.

 

가지치기의 아이디어는 간단합니다.

가능한 최대값을 이미 정답으로 가지고 있는 경우, answer = 26인 경우 더이상의 탐색을 하지않고 재귀를 끝내면 됩니다.

 

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

public class q7699_SWEA_수지의수지맞는여행 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int R, C, answer;
	static int[][] map;
	static boolean[] visit;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			answer = 0;
			st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());

			map = new int[R][C];
			visit = new boolean[26];

			for (int r = 0; r < R; r++) {
				String input = br.readLine();
				for (int c = 0; c < C; c++) {
					map[r][c] = input.charAt(c) - 'A';
				}
			}
			visit[map[0][0]] = true;
			dfs(0, 0, 1);

			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}

		System.out.println(sb);
	}

	static void dfs(int x, int y, int count) {
		if (answer == 26) {
			return;
		}
		answer = Math.max(answer, count);

		for (int i = 0; i < 4; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];

			if (isIn(nX, nY)) {
				if (!visit[map[nX][nY]]) {
					visit[map[nX][nY]] = true;
					dfs(nX, nY, count + 1);
					visit[map[nX][nY]] = false;
				}
			}
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < R && 0 <= y && y < C) {
			return true;
		}
		return false;
	}
}