[JAVA] 백준 3109 빵집 [ 백트래킹 ]

전체 코드

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


public class 백준_3106_빵집 {

	static int R, C, answer;
	static char arr[][];
	static boolean v[][];

	static int dy[] = { -1, 0, 1 }; // 방향은 대각선 위, 오른쪽, 대각선 아래로 진행
	static int dx[] = { 1, 1, 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());
		
		v = new boolean[R][C];
		
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for(int j=0; j<C; j++) {
				if(str.charAt(j) == 'x') // 벽은 true, 지나갈 수 있는곳은 false로 치환
					v[i][j] = true;
			}
		}
		for(int i=0; i<R; i++) {
//			System.out.println(i);
			backtrack(i, 0);
		}

		System.out.println(answer);
	}

	private static boolean backtrack(int y, int x) {
		
		for(int i=0; i<3; i++) {
			int ry = y + dy[i];
			int rx = x + dx[i];
			if(ry >=0 && ry < R && rx>=0 && rx< C && !v[ry][rx]) { // 범위 내에 있는지, 방문하지 않았는지 체크 
				if(rx == C-1) { // rx가 C-1이면 카운트 증가 후 종료
					answer++;
					return true;
				}
				v[ry][rx] = true; // 방문 체크
				if(backtrack(ry, rx)) // 끝까지 방문 후 다시 처음으로 돌아오기 위해 boolean 반환 형으로 구현
					return true; // true가 찍힐 경우 계속 true로 리턴되어 끝이 난다.
			}
		}
		return false; // 만약 중간에 진행할 수 있는 방향이 없다면 false로 끝까지 리턴
	}

}

 

문제 핵심 코드

private static boolean backtrack(int y, int x) {
	
	for(int i=0; i<3; i++) {
		int ry = y + dy[i];
		int rx = x + dx[i];
		if(ry >=0 && ry < R && rx>=0 && rx< C && !v[ry][rx]) { // 범위 내에 있는지, 방문하지 않았는지 체크 
			if(rx == C-1) { // rx가 C-1이면 카운트 증가 후 종료
				answer++;
				return true;
			}
			v[ry][rx] = true; // 방문 체크
			if(backtrack(ry, rx)) // 끝까지 방문 후 다시 처음으로 돌아오기 위해 boolean 반환 형으로 구현
				return true; // true가 찍힐 경우 계속 true로 리턴되어 끝이 난다.
		}
	}
	return false; // 만약 중간에 진행할 수 있는 방향이 없다면 false로 끝까지 리턴
}

 

끝까지 도달했다면 그 경로는 다시 방문하면 안되므로 방문값의 true를 유지하고,

중간에 실패했다 하더라도 대각선 위, 오른쪽 직진, 대각선 아래 순으로 진행되므로 이 후 경우의 경로에 방해를 끼치지 않으므로 방문값을 다시 false로 되돌리지 않아도 된다.

 

일반 완전탐색의 경우 모든 경우를 탐색해야하므로 true로 변환한 방문지를 false로 되돌리는 것이 맞지만

이런 백트래킹을 이용할 수 있는 문제의 경우 조건을 추가해 모든 경우가 아닌 특정 조건을 만족하는 경우만 탐색해

시간복잡도를 줄일 수 있다는 특징이 있다.

 

처음 백트래킹이라는 단어만 접했을 때는 뒤에서 부터 탐색한다는 뜻인줄 알았다.

이 의미도 맞는 말이긴 하지만, 편하게 접근하기 위해서는 '완전 탐색 시 조건을 추가해 시간을 줄여 효율 높이기' 정도로 이해하면 와닿을 것 같다!

 

문제의 특성에 맞게 완탐을 할지 백트래킹을 할지 잘 선택해보도록 하자.