[백준]3109번 빵집 - Java

문제

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

3109번: 빵집

 

풀이

1. 파이프 설치 진행 방향(필요한 것만, 순서대로 -> 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선)

2. boolena 타입의 check[][] 배열로 다음 진행 방향에 파이프를 설치할 수 있는지 확인

3. 설치가 가능하면 설치하고 check배열을 true로 바꿔준 후 solution함수 재귀 호출

4. 마지막 열에 도착할 때마다 answer++

 

코드

// 3109번 - 빵집
// https://www.acmicpc.net/problem/3109

package BAEKJOON;

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

public class Num3109_빵집 {
    static int R, C;
    static char[][] map;
    static boolean[][] check;
    // 파이프 진행 방향(오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선)
    static int[] dr = {-1, 0, 1};
    static int[] dc = {1, 1, 1};
    static int answer = 0;

    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];
        check = new boolean[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);
            }
        }

        for (int i = 0; i < R; i++) {
            check[i][0] = true;
            solution(i, 0);
        }

        System.out.println(answer);
    }

    public static boolean solution(int r, int c) {
        if (c == C - 1) {
            answer++;
            return true;
        }
        for (int i = 0; i < 3; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
                continue;
            }
            if (check[nr][nc]) {
                continue;
            }
            if (map[nr][nc] == 'x') {
                continue;
            }

            // 얘는 안됨
//            if (map[nr][nc] == '.') {
//                check[nr][nc] = true;
//                solution(nr, nc);
//                check[nr][nc] = false;
//            }

            // 얘 아니면
            if (map[nr][nc] == '.') {
                check[nr][nc] = true;
                if (solution(nr, nc)) {
                    return true;
                }
            }

            // 얘는 됨
//            check[nr][nc] = true;
//            if (solution(nr, nc)) {
//                return true;
//            }
        }
        return false;
    }
}