목차
문제
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;
}
}