[백준 3109] 빵집 / 자바 / dfs

#문제         

레벨: G2
알고리즘: dfs 
풀이시간: 1시간 
힌트 참조 유무: 유

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

---

#문제 풀이        

 

1. 왼쪽에서 오른쪽으로 움직인다.

2.  X는 갈 수 없는 곳이다. 

3. 최대한 많은 곳을 가기 위해서는 왼쪽 맨위부터 시작해 오른쪽에 놓을 수 있는 가장 위 부터 차근차근 파이프를 설치해야 한다.

 

문제에서는 말해준다. 세 방향으로 움직일 수 있다고. (오른쪽 위, 오른쪽, 오른쪽 아래 ) 그러면 dfs 탐색을 4방향{ dx = {1,0,0,-1}  dy = { 0,1,-1,0} } 처럼 오른쪽으로 가는 건 고정이니 dy = {1, 0, -1} 로 만들 수 있겠다. 여기서 놓치면 안 되는 게 dy의 순서이다. 가장 위부터 놓여야 많이 놓을 수 있으니 1,0,-1 꼭 이 순으로 탐색해야 한다.

이미 탐색한 점은 파이프를 놓는데 실패했는지 성공했는지 알았기 때문에 더 탐색 안해도 된다. 더 쉽게 말하면 성공했으면 파이프는 겹치면 안되므로 그 점을 탐색하면 안되는 거고, 실패했으면, 이미 그 점을 통해봤자 실패한 경로이기 때문에 탐색을 안 해도 된다. 그래서 탐색한 경로는 건물과 같이 'X' 로 표시할 거다.

 

그럼 (0,0) (1,0) (2,0)  .... 이렇게 차례대로 dfs하면 된다.

 

+) 값을 파라미터로 넘겨줘 전역변수를 수정하거나, 조건에 해당하면 reurn int로 해서 값을 받거나 하는 dfs문만 짜본 사람 같은 경우는 return 타입이 boolean인 dfs를 작성해볼 수 있는 문제이다.

 

---

#풀이 코드      

import java.io.*;
import java.util.*;

public class Main {
    static int R, C;
    static char[][] map;
    static int[] dy = {-1, 0, 1}; // 오른쪽 위, 오른쪽, 오른쪽 아래

    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++) {
            map[i] = br.readLine().toCharArray();
        }

        int count = 0;
        for (int i = 0; i < R; i++) {
            if (dfs(i, 0)) {
                count++;
            }
        }

        System.out.println(count);
    }

    static boolean dfs(int x, int y) {
        if (y == C - 1) {
            return true;
        }

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

            if (nx >= 0 && nx < R && ny < C && map[nx][ny] == '.') {
                map[nx][ny] = 'x'; // 방문한 곳을 표시
                if (dfs(nx, ny)) {
                    return true;
                }
                // 백트래킹하지 않음
            }
        }

        return false;
    }
}