BOJ (Java) 3109번: 빵집

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

---

풀이

dfs로 탐색하되, 최대한 많은 파이프를 연결할 수 있게 위-중간-아래의 방향으로 탐색해야 한다.

또한 방문처리 후 실패한 경로라도 되돌려놓지 않는다.

[1,1]- > [2,2] -> [2,3] 일 때 실패한다면 [2,2]에서 가는 모든 길이 실패하기에 방문한 곳은 다시 한 번 방문하지 않는다.

 

---

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int N, M;
    static char[][] map;
    static boolean[][] visited;

    public static void main(String args[]) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = bf.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);

        // input
        map = new char[N][M];
        for (int i = 0; i < N; i++) {
            String input = bf.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        visited = new boolean[N][M];
        int cnt = 0;
        
        // N개의 라인 시작점부터 탐색
        for (int i = 0; i < N; i++) {
            cnt = dfs(i, 1) ? cnt + 1 : cnt;
        }
        System.out.println(cnt);
    }

    static boolean dfs(int r, int c) {
        if (c == M) return true;
        int[] mv = {-1, 0, 1};
        for (int j = 0; j < 3; j++) {
            int nr = r + mv[j];

            if (nr < 0 || N <= nr || map[nr][c] == 'x' || visited[nr][c]) continue;
            visited[nr][c] = true;
            if (dfs(nr, c + 1)) return true; // 도달 가능하다면 true 반환
        }
        return false;
    }

}