[PS] BOJ3109 빵집 ( greedy ) with JAVA

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

3109번: 빵집

 

◎ 문제풀이

 

근처 빵집에 위치한 가스관(열)과 원웅이네 빵집의 가스관(열)을 연결하는 경로의 최대 개수를 구하는 문제이다. 

 

중요한 조건은 세 가지가 있다.

 

1) 파이프라인 연결은 중간에 건물이 있으면 연결되지 못한다. 

2) 한번 설치된 파이프라인 경로는 다른 경로와 겹치지 않는다. 

3) 파이프는 오른쪽 위, 오른쪽, 오른쪽 아래로만 설치가 가능하다. 

 

1)은 백트래킹 가자치기 조건이다.

2)는 한번 방문한 노드는 재방문하지 않는다는 의미이다.

3)은 탐색 경로이다.

 

문제는 최소경로가 아닌 경로의 개수를 구하는 것이므로 DFS 탐색을 한다. 

 

DFS 탐색을 행(row)이 0부터 r-1까지 하나씩 차례대로 DFS탐색하고 탐색경로를 오른쪽 위, 오른쪽, 오른쪽 아래 순서로 진행하면 모든 경로를 탐색할 수 있게 된다. ( greedy )

 

 

◎ 코드

package org.example.greedy;


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

//BOJ3109 빵집
public class Greedy16 {

    static int[] dr = {-1,0,1};
    static int r,c,ans;

    static int[][] graph;

    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());
        graph = new int[r][c];

        // 그래프 초기화
        for(int i=0;i<r;i++){
            char[] charArray = br.readLine().toCharArray();
            for(int j=0;j<c;j++){
                if(charArray[j] == 'x') graph[i][j] = -1;
            }
        }

        // DFS 탐색 ( 0 ~ r-1 )
        for(int i=0;i<r;i++){
            dfs(i,0);
        }

        // 출력
        System.out.println(ans);
    }

    public static boolean dfs( int row, int col ){
        boolean flag = false;
        
        // 끝열에 도달한 경우
        if(col == c-1){
            ans += 1;
            return true; // true 리턴
        }

        // 오른쪽위, 오른쪽, 오른쪽 아래 순으로 탐색
        for(int i=0;i<3;i++){

            int nRow = row + dr[i];
            int nCol = col + 1;

            if(isValidate(nRow, nCol) && graph[nRow][nCol] != -1){
                // 건물이거나 누가 방문해서 실패했거나 성공했거나
                // 재방문해도 의미가 없으므로 -1로 설정한 후 다시 원복할 필요없다. 
                graph[nRow][nCol] = -1; 
                
                // dfs 탐색
                if(dfs(nRow,nCol)) {
                    flag = true;
                    // 탐색을 완료하면 경로가 겹치면 안되므로 break
                    break;
                }
            }
        }

        if(flag) return true;
        else return false;
    }

    public static boolean isValidate(int row, int col){
        if(row>=0 && col>=0 && row < r && col< c) return true;
        else return false;
    }
}