[BaekJoon] 3108번 빵집 (Java) 문제 풀이 [Gold 2]

문제

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

3109번: 빵집

 

어떻게 풀 것인가?

문제를 읽어보면 그래프DFS 관련된 문제라는 것을 알 수 있다. 다만, 문제의 경우 문제 요구 사항을 보면 그리디를 요구한다.

가스관과 빵집을 연결하는 파이프라인의 최대 개수로 나올 수 있는 방법은 무엇일까에 대해서 고민을 많이했다.

 

그래서 열을 이용한다는 것에 착안하였다. 결국엔 위에서부터 차근차근 되는 것부터 게산하면 된다. (이것이 그리디인가 싶다.)

 

배열 한 곳에서 오른쪽 위, 오른쪽, 오른쪽 아래 순서로 탐색하면서 재귀를 호출(DFS) 한 번 탐색했는데, 실패한 곳은 다시 가지않는다.

 

이런식으로 끊임없이 재귀를 호출하면 결국엔 마지막에는 되는 것만 result를 통해서 숫자를 증가시키면 된다.

 

조금 설명이 부족했는데, 아래에 참고에서 블로그 풀이를 참고하면 이해가 될 것이다.

 

풀면서 놓쳤던점

오랜만에 문제를 풀다보니 문제의 감을 잃은 듯 하다..

다시금 문제를 푸는 연습을 진행해야할 것 같다.

 

이 문제를 통해 얻어갈 것

DFS의 재귀방법

 

내 코드 

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

// 백준알고리즘 3109번 빵집
public class Main {
    static int N, M;
    static char[][] arr;

    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new char[N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        result = 0;
        for (int i = 0; i < N; i++)
            if (check(i, 0))
                result++;
        System.out.println(result);


    }

    public static boolean check(int x, int y) {
        arr[x][y] = '-';
        if (y == M - 1)
            return true;

        if (x > 0 && arr[x - 1][y + 1] == '.')
            if (check(x - 1, y + 1))
                return true;
        if (arr[x][y + 1] == '.')
            if (check(x, y + 1))
                return true;
        if (x + 1 < N && arr[x + 1][y + 1] == '.')
            if (check(x + 1, y + 1))
                return true;
        return false;
    }
}

 

참고

https://wiselog.tistory.com/140

[백준 3109] 빵집(Java)