[BOJ] 빵집(JAVA)

[3109] 빵집

www.acmicpc.net/problem/3109

 

Solution

• 간단한 백트래킹 문제인데, 처음에 문제를 보고 고려하지 않아도 될 부분에 대해서 오래 생각해서 시간이 걸렸다.
• 파이프는 우상향, 우, 우하향으로만 연결될 수 있기 때문에 dfs로 파이프를 연결하다 보면 자연스럽게 우상향으로 파이프는 그려진다. 
• 처음에 잘못 생각했던 부분이 (0~i행에서 시작하는)위에 있는 파이프가 아래로 내려와 그려졌을 때 (i+1~r행)아래행에서 더많이 연결될 수 있음에도 불구하고 연결하지 못하는 경우가 있을거라고 생각했다.
• dfs 메서드가 다음 칸으로 연결될 수 있을 때만 true를 리턴하도록 만들어서 가장 처음 파이프가 연결된 경우를 제외하고는 map에 그려지지 않고 false를 리턴한다.
• 반복문 안에서 true값을 리턴하기 때문에 다음 방향은 고려되지 않는다.

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int r, c, answer;
    static int[][] map;
    static int[] d = {-1, 0, 1};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = stoi(st.nextToken());
        c = stoi(st.nextToken());
 
        map = new int[r][c];
        for (int i = 0; i < r; i++) {
            String line = br.readLine();
            for (int j = 0; j < c; j++) {
                if (line.charAt(j) == '.') {
                    map[i][j] = 0;
                } else {
                    map[i][j] = 1;
                }
            }
        }
 
        answer = 0;
        for (int i = 0; i < r; i++) {
            if (dfs(i, 0)) answer++;
        }
        System.out.println(answer);
    }
 
    private static boolean dfs(int row, int col) {
        if (col == c - 1) {
            return true;
        }
 
        for (int i = 0; i < d.length; i++) {
            int nx = row + d[i];
            int ny = col + 1;
 
            if (isRange(nx, ny) && map[nx][ny] == 0) {
                map[nx][ny] = 1;
                if (dfs(nx, ny)) return true;
            }
        }
        return false;
    }
 
    private static boolean isRange(int nx, int ny) {
        if (nx >= 0 && ny >= 0 && nx < r && ny < c)
            return true;
        return false;
    }
 
    private static int stoi(String s) {
        return Integer.parseInt(s);
    }
}