[백준] 3109 빵집 - Java

처음엔 이동거리가 최댄 줄 알고 시간 좀 잡아먹었다. 문제 잘 읽기.....

문제 해결 방안 

- 원웅이 (행, 0)부터 검사해준다 (오른쪽, 오른쪽 대각, 오른쪽 위)

- 재귀를 돌릴 때 방문한 위치는 건물을 세운다 ex) map [x][y] ='x' 이렇게 해도 되고 boolean [][] visit =true로 바꾼다

- 오른쪽 오른쪽 대각, 오른쪽 위 수식을 세워준다.

- 빵집 즉 마지막 열에 닿으면 이건 파이프가 연결되었다는 뜻이다. 

- 더 이상 조건 건물이 있거나 방문한 점이라서 갈 곳이 없으면 이건 파이프가 연결되지 못한다는 뜻이다.

- 그림으로 표현하면 이와 같이 되는 거 같다.

- 마지막 행 (4,0) 을 보게 되면 다 방문했어서 갈때가 없다.

 

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

public class Main {
	static int R, C;
	static char[][] map;

	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());
		map = new char[R][C];
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		int count = 0;
		for (int i = 0; i < R; i++) {
			if (backTracking(i, 0)) {
				count++;
			}else {
			}
		}

		System.out.println(count);

	}

	static boolean backTracking(int x, int y) {
		map[x][y] = 'x';// 갔던 곳은 방문 못하게 해야함
		if (y == C - 1) {// 빵집 도착 바로 리턴
			return true;
		}
		if (x > 0 && map[x - 1][y + 1] == '.') { // 오른쪽 위
			if (backTracking(x - 1, y + 1)) {
				return true;
			}
		}
		if (map[x][y + 1] == '.') {// 오른쪽
			if (backTracking(x, y + 1)) {
				return true;
			}
		}
		if (x + 1 < R && map[x + 1][y + 1] == '.') { // 오른쪽 아래
			if (backTracking(x + 1, y + 1)) {
				return true;
			}
		}
		
		return false;
	}
}