[백준] 3109번 / Java / 빵집

문제 - (https://www.acmicpc.net/problem/3109)

백트래킹 문제다

각 행의 0열부터 재귀를 시작해가면서

파이프를 연결하는 것이 한 번이라도 성공하면 그 재귀는 종료시킨다

그리고 다음 행의 0열부터 다시 파이프를 연결한다.

이때, 전 행의 0열부터 연결해왔던 파이프는 visited배열에 표시가 되어 있으므로

파이프를 연결했던 곳은 다시 가지 않으면서 재귀를 진행한다

---

📌주의할 점

• 파이프는 무조건 오른쪽 위, 오른쪽, 오른쪽 아래 방향을 순서로 향하게 해서 연결을 시도해야 한다. 잘 생각해보면 무조건 오른쪽 방향으로만 파이프를 연결할 수 있는 조건 때문에 앞서 말한 방향을 순서로 연결해야 최대한 많은 파이프를 연결할 수 있다.

 

---

---

코드

package algorithm.etc;

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

public class Restaurant {
    static int r, c;
    static char[][] map;
    static int answer;
    static int[] dy = {-1, 0, 1}; //오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선으로 연결
    static boolean[][] visited;

    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());
        map = new char[r][];
        visited = new boolean[r][c];

        for (int i = 0; i < r; i++) {
            map[i] = br.readLine().toCharArray();
        }

        // 첫째열과 마지막열은 각각 수도관과 식당이므로 비어있음
        for (int i = 0; i < r; i++) {
            connect(i, 0);
        }
        System.out.println(answer);
    }

    public static boolean connect(int y, int x) {
        // 기저 : 이동하다가 마지막 열에 도착하면 종료
        visited[y][x] = true;
        if (x == c - 1) {
            answer++;
            return true;
        }

        for (int d = 0; d < 3; d++) {
            int ny = y + dy[d];
            int nx = x + 1;
            if (ny < 0 || ny >= r) continue;
            if (map[ny][nx] == 'x' || visited[ny][nx]) continue; // 건물이 있으면 갈 수 없음, 이미 파이프가 놓인 자리도 갈 수 없음
            if (connect(ny, nx)) return true; // 한번이라도 연결된다면 재귀종료
        }
        return false;
    }
}