[*3109*] 빵집 in Java ( + Backtracking, DFS )

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

3109번: 빵집

---

문제 요약

격자 크기 :R X C
map[r][0] = 근처 빵집의 가스관
map[r][c-1]= 원웅이 빵집
건물에는 파이프를 놓을 수 없다. 
. : 빈칸, x :건물


파이프라인 시작위치 : 첫째 열에서 시작
파이프라인 도착위치 : 마지막 열
연결 가능 위치 :↗, →, ↘
파이프라인의 경로는 겹칠 수 없고, 서로 접할수도 없다. == 각 칸을 지나는 파이프는 하나여야한다. 

가스를 되도록 많이 훔치려고 한다.

 (= 연결하는 파이프라인의 최대 개수를 구하시오)

---

문제 접근 방법

- ↗, →, ↘ 순으로 탐색을 진행한다.

왜냐하면 아래에 설치할 파이프라인을 위해서다!

위쪽을 우선순위로 두고 탐색을 하면

아래쪽에 더 많은 파이프를 설치할 수 있기 때문이다!

 

-  백트래킹 기법을 사용한다.

마지막 열에 도착하면, 파이프라인을 구축한 것이므로

남아있는 dfs는 수행하지 않고

모두 종료시킨다.

 

---

시행 착오

1. 마지막 열에 도착하여 파이프 라인을 구축했을 때

수행되기를 기다리고 있는 dfs들을 종료시키는 방식에 대해

구현하는 과정에서 어려움을 겪었다.

 

이 부분은 dfs 함수의 형식을 boolean으로 바꿔주고

마지막 열에 도착했을 때 return true를 넘겨준다.

그리고 dfs를 실행할 때 해당 리턴값이 true이면 

이미 파이프라인을 구축한 상태이기 때문에

더이상 작업을 진행할 필요가 없으므로

return true를 넘겨줌으로써

뒤에 줄줄이 기다리는 dfs들을 종료시켜준다.

 

 

void 방식으로도 비슷하게 짤 수 있다.

 

 

 

---

소스코드

 

1. dfs를 boolean 형식으로 작성한 코드

package day_0818;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class n3109 {
    static int R,C; // 행, 열
    static char[][] map;
    static ArrayList<Integer> startRowList;
    static int [] dxs= {-1,0,1}; // ↗, →, ↘
    static int answer;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map=new char[R][C];
        startRowList=new ArrayList<>();
        answer=0;
        
        // 맵 입력받기
        for (int i = 0; i < R; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                map[i][j]= temp[j];
                
            }
            if(temp[0]=='.') {
                startRowList.add(i);
            }
        }
        for (int i = 0; i < R; i++) {
            if(dfs(i,0)) answer++; // x, y
        }
        System.out.println(answer);
        
    }
 
    private static boolean dfs(int x, int y) {
        if(y==C-1) {
            return true; // 해당라인 파이프라인 구축 완료, 다음 행으로 넘어가기 위한 작업
        }
        
        for (int i = 0; i < 3; i++) {
            int nx=x+dxs[i];
            int ny=y+1;
            if(canGo(nx, ny)) {
                map[nx][ny]='x';
                if(dfs(nx,ny)) { // 뒤로 가기
                    return true;
                };
                
            }
        }
        return false;
    }
 
    private static boolean canGo(int x, int y) {
        if (x>=0 && x<R && y>=0 && y<C && map[x][y]!='x') {
            return true;
        }
        return false;
    }
 
}
 

 

 

2. dfs를 void 형식으로 작성한 코드

package day_0818;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class n3109 {
    static int R,C; // 행, 열
    static char[][] map;
    static ArrayList<Integer> startRowList;
    static int [] dxs= {-1,0,1}; // ↗, →, ↘
    static int answer;
    static boolean btn;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map=new char[R][C];
        startRowList=new ArrayList<>();
        answer=0;
        
        // 맵 입력받기
        for (int i = 0; i < R; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                map[i][j]= temp[j];
                
            }
            if(temp[0]=='.') {
                startRowList.add(i);
            }
        }
        for (int i = 0; i < R; i++) {
            btn=false;
            dfs(i,0);
        }
        System.out.println(answer);
        
    }
 
    private static void dfs(int x, int y) {
        if (btn==true) return; // 연결되어 있으면 모든 dfs를 종료한다.
        map[x][y]='x';
        
        if(y==C-1) {
            answer++; // x, y
            btn=true;
            return; // 해당라인 파이프라인 구축 완료, 다음 행으로 넘어가기 위한 작업
        }
        
        for (int i = 0; i < 3; i++) {
            int nx=x+dxs[i];
            int ny=y+1;
            if(canGo(nx, ny)) {
                dfs(nx,ny);
            }
        }
    }
 
    private static boolean canGo(int x, int y) {
        if (x>=0 && x<R && y>=0 && y<C && map[x][y]=='.') {
            return true;
        }
        return false;
    }
}