3109 - 빵집(G2)

문제

https://www.acmicpc.net/problem/3109

풀이

문제를 읽어 보자면, 단순 탐색의 시간 복잡도는 3^c * R임을 알 수 있다.
최악의 경우를 고려하면 시간 초과가 날 것이다.

파이프는 겹쳐있을 수 없으므로 성공한 파이프는 그 자리에 유지시켜야 한다.
따라서 파이프가 있는 자리를 따로 표시해야 한다.

일반적으로 for 반복을 돌려 현재 자리에 파이프가 있는 지 체크하고, 파이프가 없다면 파이프를 놓은 뒤 조건이 맞지 않는다면 파이프 되돌리기를 수행한다. (백트래킹)
하지만 해당 문제에서는 이런 방식을 하면 안 되는데 이는 이전 백트래킹에서 새로운 경우의 수를 찾는 과정에서 똑같은 실패 과정을 반복하기 때문이다 (위, 아래, 중간의 세 방향이 있기에 실패가 겹칠 수 있음.)

중요한 사실은 파이프가 성공하든 실패하든 경로를 유지시킨다는 점이다.

따라서 일반적으로 방문 체크를 하는 것이 아니라, 중복 반복한 경우를 체크하여야 한다.
이후 목적인 '가장 많은 파이프를 설치'하는 방법을 설계한다.
(위/중간/아래) 중 위쪽 방향을 먼저 진행하여 푸는 것을 고안하였다.

소스 코드

public class BOJ_3109_빵집 {

	static int R, C, ans;
	static char[][] map;
	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 char[R][];
		for (int i = 0; i < R; i++) map[i] = br.readLine().toCharArray();
		for (int i = 0; i < R; i++) dfs(i, 0); //열은 항상 입력값부터 시작함
		System.out.println(ans);
	}
	
	static int[] dr = {-1, 0, 1}; //U, 0, D
	private static boolean dfs(int r, int c) {
		map[r][c] = 'x';	//현재 위치 파이프 깔음
		if (c == C - 1)	{	//도착 기저조건
			ans++;	//성공 - 이후에 다른 재귀가 이루어지므로 return만 하는 것이 아닌 T/F로 값을 알려준다.
			return true; //T라면 나머지 dfs를 하지 않아야 한다. -> dfs() 함수 실행을 TF로 구분한다.
		}
		 
		int nr, nc = c + 1;
		for (int d = 0; d < 3; d++) {
			nr = r + dr[d];
			if (nr < 0 || nr >= R || map[nr][nc] == 'x') continue;
			
			if (dfs(nr, nc)) return true; //다음 위치로 가기 - 기저조건 확인 - 리턴값이 True면 재귀를 전부 리턴하면서 끝낸다.
		}
		return false;
	}
}