[백준]BJ_G2_3109_빵집

BJ_G2_3109_빵집

 

 

문제링크

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

3109번: 빵집

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=Jk6JI02psRk 

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l2;

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

/**
 * @author 은서파
 * @see https://www.acmicpc.net/problem/3109
 * @mem 53508 KB
 * @time 308 ms
 * @caution
 * #백트래킹,
 * 선으로 된 탐색 결과를 면으로 표현해보고,
 * 탐색 시 최대 파이프가 되기 위한 연결 방식 고민해보고,
 * 우측 벽에 도달하면 종료하도록 재귀 구성할 것
 * 왼쪽으로는 다시 탐색하지 않기 때문에 visited를 고민할 필요가 없다.
 * 대신 파이프가 한 영역에 하나만 지날 수 있으므로 방문 완료한 지점은 X로 처리해버리자.
 * 왔던 길을 다지 지우지 않는 것이 핵심 백트래킹
 */
public class BJ_G2_3109_빵집 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    private static int answer, R, C;

    // 탐색 방향도 아주 중요한 문제이다. - 컬럼이 증가하면서 위, 중간, 아래로 탐색해야 한다.
    private static int[] dir = {-1, 0, 1};

    private static char[][] map;

    public static void main(String[] args) throws NumberFormatException, IOException {
        input = new BufferedReader(new StringReader(src));

        tokens = new StringTokenizer(input.readLine(), " ");
        R = Integer.parseInt(tokens.nextToken());
        C = Integer.parseInt(tokens.nextToken());

        map = new char[R][];

        for (int r = 0; r < R; r++) {
            map[r] = input.readLine().toCharArray();
        }
        // 입력 완료
        
        // 각 row 별로 dfs 해보자.
        for (int r = 0; r < R; r++) {
            if (makePipe(r, 0)) {
                //System.out.println(r);
                answer++;
            }
        }
        System.out.println(answer);
    }

    private static boolean makePipe(int r, int c) {
        // 방문한 곳이 C-1 지점이면 끝이다.!!
        if (c == C - 1) {
            return true;
        }

        for (int d = 0; d < dir.length; d++) {
            int nr = r + dir[d];
            int nc = c + 1;
            if (isIn(nr, nc) && map[nr][nc] == '.') {
                map[nr][nc] = 'x';
                boolean result = makePipe(nr, nc);
                // 성공이면 종료, 실패면 다음 턴의 재귀 진행
                if (result) {
                    return true;
                }
                // 여기가 바로 가지치기 되돌리면 안된다!!
                // map[nr][nc] = '.';
                // 맵을 다시 되돌려 버리면 다음 탐색에서 불필요한 길을 다시 가게 된다.
                // 어차피 위에서 순차적으로 접근하고 있고 첫번 탐색에서 결정된 시나리오는 두번째 탐색에도 동일하다.
            }
        }
        return false;
    }



    public static boolean isIn(int r, int c) {
        return 0 <= r && 0 <= c && r < R && c < C;
    }

    private static String src = "5 5\r\n" +
                                ".xx..\r\n" +
                                "..x..\r\n" +
                                ".....\r\n" +
                                "...x.\r\n" +
                                "...x.";
}