백준 알고리즘 3109번 - 빵집 [Java]

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

3109번: 빵집

 

 

DFS + 그리디 문제이다

 

문제 푸는데 오래 걸렸지만 막상 코드 보면 설명할 내용은 없는 것 같다

 

다른 탐색과는 다르게 방향을 지정하는 delta 배열에서

 

값을 넣어주는 순서가 중요하다는 정도?

 

그리디로 풀어야하기 때문에 오른쪽 위 / 오른쪽 / 오른쪽 아래 순서로 탐색하면 된다

 

 

 

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

public class Main {

    static int R, C, ANS;
    static char map[][];
    static int deltas[][] = {
            {-1, 1},
            {0, 1},
            {1, 1}
    };

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String str;
        int i, j;

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];

        for(i=0; i<R; i++) {
            str = br.readLine();
            for(j=0; j<C; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        for(i=0; i<R; i++) {
            solve(i, 0);
        }

        System.out.println(ANS);
    }


    public static boolean solve(int r, int c) {

        map[r][c] = '!';

        if(c == C-1) {
            ANS++;
            return true;
        }

        int dr, dc;
        boolean flag = false;

        for(int d=0; d<3; d++) {

            dr = r + deltas[d][0];
            dc = c + deltas[d][1];

            if(dr >= 0 && dr < R && dc >=0 && dc < C) {
                if(map[dr][dc] == '.') {
                    flag = solve(dr, dc);

                    if(flag)
                        break;
                }
            }
        }

        return flag;
    }

}

 

배관을 끝까지 연결했는지 확인할 flag를 하나 만들고

 

마지막 열에 도달했으면 flag를 true로 지정한 다음 리턴한다

 

생각하기는 어려웠는데 막상 코드를 보니 되게 간단하다는 생각이 많이 든다..

 

정답으로 잘 나온다

 

 

 

5 7
.x...x.
.x...x.
.x.....
.......
.......

ans 2

100 5
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
...x.
...x.
.....
...x.
...x.
...x.
.....
.....
..x..
..x..
.....
..x..
.....
..x..
.....

ans 92

5 5
.xx..
..x..
.....
...x.
...x.

ans 2