[PS] 백준3109 : 빵집 (Java)

문제

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

---

풀이

그리디 + DFS

접근법

처음 접근은 완전탐색 방식으로 접근했습니다.

문제를 해석해보면 왼쪽 열에서 오른쪽 열까지 벽(x)을 제외한 나머지 통로들에 파이프를 설치하여 연결할 수 있는 길의 개수를 구하는 문제입니다.

주어진 조건에 의한 행동은 3가지로 다음과 같습니다.

1. 오른쪽 상단 대각선
2. 오른쪽
3. 오른쪽 하단 대각선

또한 겹치게 설치 할 순 없다는 조건이 있습니다.

탐색해야하는 경우의 수는 그럼 총 N개로 시작 열의 격자칸 개수만큼 탐색을 해야합니다.

또한 백트래킹을 통해서 완성된 길에 대해서는 기록을 하고, 끝까지 도달하지 못하는 경우에는 원상복귀를 시켜야 한다고 생각했습니다.

위와같은 로직을 구현하기 위해서 처음 0,0에서 탐색을 시작하여 길이 완성될 경우 다음 지점에 대해서 탐색을 시작하는 방식으로 재귀함수를 구현했습니다.

이렇게 구현한 이유로는 이전 격자칸에서 어떤식으로 파이프를 설치하냐에 다음 격자칸의 출발에서 영향을 줄 수 있다고 생각했기 때문입니다.

또한 그리디로는 다음과 같이 생각했습니다.

0에서 시작하면 최대한 위로 탐색
N-1에서 시작하면 최대한 아래로 탐색

이렇게 구현할 경우 시간초과가 발생하게 됨으로 완전탐색으로는 풀지 못하는걸 알 수 있었습니다.

 

그러면 완전탐색을 하되 줄일 수 있는 부분에 대해서는 그리디 알고리즘을 적용하여 명제를 적용해야했습니다.

다음은 추가되는 명제에 대한 설명입니다.

1. 각 격자칸에서 한번 탐색된 경로에 대해서는 다음 격자칸에서도 탐색할 필요가 없다.
   1. 이유는 해당 경로가 끝까지 탐색되지 못하는 경로라면 다음 격자칸에서 또한 마찬가지로 끝까지 탐색하지 못하기 때문입니다.
2. 처음 그리디 생각과 동일하게 최대한 위로(혹은 아래로) 탐색하되, 처음 끝까지 도달한 경로에 대해서 방문체크를 하고, 다음 경로에 대해서는 탐색할 필요가 없습니다.
   1. 이를 위한 DFS 재귀에서 중간에 탐색을 멈추는 방법을 생각할 필요가 있습니다.

사실 첫번째 명제가 그리디를 적용하여 시간복잡도를 현저하게 낮출 수 있는 방법이고, 정해라고 생각합니다.

다음은 위 그리디 알고리즘을 적용하여 작성한 정답코드입니다.

 

---

소스코드

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

//BOJ_3109
public class Main {
    static int N, M, res;
    static char[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        /**
         * 0에서 시작하면 최대한 위로 탐색
         * N-1에서 시작하면 최대한 아래로 탐색
         * 생각 못했던 것 : 백트래킹으로 지나간 경로를 되돌릴 필요가 없다. (그 지점에서 못갔던 경로라면 다른 지점에서도 못감)
         * 해결법
         * 각 지점에서 최대한 위로 탐색해서 N-1에 도착하면 경로 기록
         * 도착하지 못하면 지나온 경로에 대해 모두 방문체크
         * DFS에서 특정지점부터 깊이탐색을 중단하는 방법?
         * **/

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for(int i=0; i<N; i++) {
            if(dfs(i,0)) res++;
        }

        System.out.println(res);
    }

    private static boolean dfs(int x, int y) {
        map[x][y] = 'o';
        if(y == M-1) {
            return true;
        }

        int nx = x -1, ny = y + 1;
        if(isRange(nx, ny) && map[nx][ny] == '.') {
            if(dfs(nx,ny)) return true;
        }

        nx = x; ny = y + 1;
        if(isRange(nx, ny) && map[nx][ny] == '.') {
            if(dfs(nx,ny)) return true;
        }
        nx = x + 1; ny = y + 1;
        if(isRange(nx, ny) && map[nx][ny] == '.') {
            if(dfs(nx,ny)) return true;
        }

        return false;

    }

    private static boolean isRange(int x, int y) {
        if(x<0 || y<0 || x>=N || y>=M) return false;
        return true;
    }

}

---

정리

깊이우선탐색(DFS) 알고리즘을 완전탐색만을 위한 알고리즘이라 생각하여 이러한 그리디 알고리즘을 같이 적용하여 푸는 문제에 익숙하지 않았던 것 같습니다.

조금 더 공부하게 된다면, 많은 문제를 풀어보고 그리디 알고리즘에 대한 파악하는 숙련도와 명제를 세우는 연습을 더 해야될 것 같다고 많이 생각하게 해준 문제 였습니다.

 

두번 헤매는 경우는 없도록 잘 정리하고 복기하여 문제해결능력을 키워야겠습니다!..