빵집 - 3109번

---

풀이 방법

최단 경로를 찾는 문제가 아닌 겹치지 않는 모든 경로를 찾는 문제이다.

위에서부터 탐색해서 경로를 찾으면 return 시켜주는 방식으로 풀이했고 경로를 찾지 못하게 되면 visited를 false로 바꾸는 것이 아니라 그 길로 가게되면 경로를 찾을 수 없기 때문에 true 상태로 남겨두었습니다.

 

내 코드

import java.io.*;
import java.util.*;

public class Main {
	static char[][] arr;
	static int R, C, count;
	static int[] direct = { -1, 0, 1 };
	static boolean[][] visited;
	static boolean check;

	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());
		count = 0;

		arr = new char[R][C];
		visited = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			String s = br.readLine();
			for (int j = 0; j < C; j++) {
				arr[i][j] = s.charAt(j);
			}
		}

		for (int i = 1; i < R; i++) {
			if(arr[i][0] == '.') {
				check = false;
				dfs(i, 0);
			}
		}
		System.out.println(count);
	}

	static void dfs(int x, int y) {

		if (y == C - 2) {
			count++;
			check = true;
			return;
		}

		for (int i = 0; i < 3; i++) {
			int nextX = x + direct[i];
			int nextY = y + 1;

			if (nextX >= 0 && nextX < R && arr[nextX][nextY] == '.' && !visited[nextX][nextY]) {
				visited[nextX][nextY] = true;
				dfs(nextX, nextY);
				if (check) {
					return;
				}
			}
		}
	}
}