[BOJ/Java] 3109 빵집

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

public class Main {

	static char[][] grid;
	static int cnt, r, c;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		grid = new char[r][];
		for (int i = 0; i < r; i++) {
			grid[i] = br.readLine().toCharArray();
		}
		cnt = 0;
		for (int i = 0; i < r; i++) {
			connect(i, 0);
		}
		System.out.println(cnt);
	}

	static boolean connect(int y, int x) {
		if (x == c - 1) {
			cnt++;
			return true;
		}
		for (int i = -1; i < 2; i++) {
			int ny = y + i;
			int nx = x + 1;
			if (ny >= 0 && nx >= 0 && ny < r && nx < c && grid[ny][nx] == '.') {
				grid[ny][nx] = 'x'; 
				if (connect(ny, nx))
					return true; 
			}
		}
		return false;
	}
}

솔직히 제대로 못풀어낸 문제.. 

우상 > 우  > 우하의 우선순위가 있다는 생각을 못하고 모든 경우의 수를 고려하다 보니 너무 어렵게 생각하고 풀다가 꼬여버렸다
boolean으로  파이프 완성 여부를 알려줄 수 있다는 생각도 못했다.
backtracking에서는 boolean 이용해주는게 중요하겠구나