[백준] 3109 빵집

📖 문제

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

💻 내 코드

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

public class Main {

	static String[][] map;
	static int R, C, total;
	static int[] dx = { -1,0, 1 };
	static boolean check;

	public static void main(String[] args) throws IOException {
		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());

		map = new String[R][C];

		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().split("");
		}

		total=0;
		for (int i = 0; i < R; i++) {
			check=false;
			if(find(i, 0))
				total++;
		}
		System.out.println(total);

	}

	private static boolean find(int x, int y) {

		if (y == C - 1) {
			check=true;
			return true;
		}

		for (int i = 0; i < 3; i++) {
			int nx = x + dx[i];
			int ny = y + 1;

			if (0 <= nx && nx < R && 0 <= ny && ny < C ) {
				if(map[nx][ny].equals(".")) {
					map[nx][ny] = "x";
					find(nx, ny);
					if(check)
						return true;
				}
			}
		}

		return false;

	}
}

💡 풀이

• 0행에서 출발해서 마지막행까지 가야한다
• 위쪽부터 체크
• 만약 마지막행인 C-1에 도달했다면 true반환
• 아니라면 오른쪽, 오른쪽 위, 오른쪽 아래로 이동
• 만약 이동한 위치에 아무것도 없다면 다시 방문하지 못하도록 다른 문자로 바꾸고 그 위치에서 다시 이동
• 만약 이미 한 방향으로 가서 마지막 행에 도달했다면 true를 반환했을 것이므로 그 위치에서의 결과가 true라면 true 반환하고 멈춤