- 깊이우선탐색(dfs)과 Backtracking 기법을 적용하였다.
- dxdy 배열은 우상, 우, 우하 순서를 고려하여 선언하였다.
- 방문 체크는 따로 배열을 만들지 않고 기존 pipe 배열에 'O'값을 넣었다.
- dfs() 함수의 리턴값으로 boolean형을 주어 해당 경로가 성공인지 실패인지 구분하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int R, C;
static int[][] dxdy = { {-1, 1}, {0, 1}, {1, 1} };
static int ans;
static char[][] pipe;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
R = Integer.parseInt(input[0]);
C = Integer.parseInt(input[1]);
pipe = new char[R][C];
for (int i = 0; i < R; i++) {
String tmp = br.readLine();
for (int j = 0; j < C; j++) {
pipe[i][j] = tmp.charAt(j);
}
}
for (int i = 0; i < R; i++)
dfs(i, 0);
System.out.println(ans);
}
static boolean dfs(int x, int y) {
int nx, ny;
if(y == C-1) {
ans++;
return true;
}
for (int i = 0; i < 3; i++) {
nx = x+dxdy[i][0];
ny = y+dxdy[i][1];
if(nx<0 || nx>=R || ny>=C || pipe[nx][ny] != '.') continue;
pipe[nx][ny] = 'O';
if(dfs(nx, ny)) return true;
}
return false;
}
}