[알고리즘] 빵집

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

3109번: 빵집

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

public class Main {

	static int[][] graph;
	static int[] dx = { -1, 0, 1 };
	static int[] dy = { 1, 1, 1 };
	static int R;
	static int C;
	static int count = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		graph = new int[R][C];
		for (int i = 0; i < R; i++) {
			String line = br.readLine();
			for (int j = 0; j < C; j++) {
				if (line.charAt(j) == 'x') {
					graph[i][j] = -1;
				} else {
					graph[i][j] = 0;
				}
			}
		}

		for (int i = 0; i < R; i++) {
			dfs(i, 0);
		}
		System.out.println(count);
	}

	private static boolean dfs(int row, int col) {
		if (col == C - 1) {
			count++;
			return true;
		}
		for (int i = 0; i < 3; i++) {
			int nRow = row + dx[i];
			int nCol = col + dy[i];
			if (!(0 <= nRow && nRow < R && 0 <= nCol && nCol < C)) {
				continue;
			}
			if (graph[nRow][nCol] == 0) {
				graph[nRow][nCol] = 1;
				if (dfs(nRow, nCol)) {
					return true;
				}
			}
		}
		return false;
	}
}

나의 풀이

- 일단 제일 오른쪽 열에 도달하면 그게 최선인게 보장이 되기 때문에 가능한 문제