[백준] 알고리즘 분류(그리디 알고리즘,JAVA)3109번, 빵집

문제 링크

3109번: 빵집

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 첫째 열은 근처 빵잡 가스관, 마지막 열은 원웅이네 가스관입니다.

2. 파이프는 3가지 방향(↗, →, ↘)으로 설치가 가능합니다.

3. 'X'는 건물, '.'는 빈 칸이며, 건물에는 파이프를 설치가 불가능합니다.

4. 파이프 라인의 최대 개수를 결과로 출력합니다.

5. 파이프 경로는 겹칠 수 없으며, 서로 접할 수도 없습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. DFS에서 그리드 알고리즘을 혼합하여 탐색을 진행합니다.

 

3. 탐색이 끝난 뒤 만들어진 파이프 라인의 개수를 결과로 출력합니다. 

 

 

DFS 탐색.

파이프 라인을 최대의 개수로 만드려면 한쪽 방향으로 정렬되도록 연결되어야 합니다.

 

※ 저는 위쪽 방향으로 정렬되도록 DFS를 설계하였습니다.

 

위쪽 방향으로 정렬되기 위해서 파이프를 연결하는 우선순위는 ↗, →, ↘로 하였습니다.

 

아래와 같은 상태일 때

 

.	X	.	.	.
.	.	.	.	.
.	.	.	.	.

 

.(↘)	X	.(→)	.(→)	.(도착)
.	.(↗)	.	.	.
.	.	.	.	.

 

.(연결)	X	.(연결)	.(연결)	.(연결)
.(↘)	.(연결)	.(→)	.(→)	.(도착)
.	.(↗)	.	.	.

2개의 파이프 라인을 얻을 수 있습니다.

※ 저는 위쪽 방향으로 정렬되도록 하였으므로 DFS탐색도 위쪽부터 진행하도록 합니다.

 

DFS탐색할 때 방문 확인을 위하여 Boolean[][]을 사용하실 때 파이프 라인이 완성되지 않았을 때 방문한 공간을 false로 풀어주실 필요가 없습니다.

 

이유 : 파이프 라인이 근처에 다른 방법으로 연결되었을 것이므로 해당 공간에 파이프를 놓아도 파이프 라인을 완성시킬 수 없기 때문입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

R : 5

C : 5

 

.	X	X	.	.
.	.	X	.	.
.	.	.	.	.
.	.	.	X	.
.	.	.	X	.

 

2. DFS에서 그리드 알고리즘을 혼합하여 탐색을 진행합니다.

(0, 0) DFS탐색!

 

.(↘)	X	X	.	.(도착)
.	.(↘)	X	.(↗)	.
.	.	.(↗)	.	.
.	.	.	X	.
.	.	.	X	.

파이프 라인 완성!

 

(1, 0) DFS탐색!

 

.(연결)	X	X	.	.(연결)
.(↘)	.(연결)	X	.(연결)	.(도착)
.	.(↘)	.(연결)	.(↗)	.
.	.	.(↗)	X	.
.	.	.	X	.

파이프 라인 완성!

 

(2, 0) DFS탐색!

.(연결)	X	X	.	.(연결)
.(연결)	.(연결)	X	.(연결)	.(연결)
.(↘)	.(연결)	.(연결)	.(연결)	.
.	.(↘)	.(연결)	X	.
.	.	.(X)	X	.

파이프 라인 실패!

 

(3, 0) DFS탐색!

 

.(연결)	X	X	.	.(연결)
.(연결)	.(연결)	X	.(연결)	.(연결)
.(방문)	.(연결)	.(연결)	.(연결)	.
.(↘)	.(방문)	.(연결)	X	.
.	.(X)	.(방문)	X	.

파이프 라인 실패!

(3, 0) DFS탐색!

 

.(연결)	X	X	.	.(연결)
.(연결)	.(연결)	X	.(연결)	.(연결)
.(방문)	.(연결)	.(연결)	.(연결)	.
.(방문)	.(방문)	.(연결)	X	.
.(X)	.(방문)	.(방문)	X	.

파이프 라인 실패!

 

3. 탐색이 끝난 뒤 만들어진 파이프 라인의 개수를 결과로 출력합니다. 

 

파이프 라인 2개 완성!

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 격자 (0, 0)부터 아래 방향으로 dfs함수를 실행하여 파이프 라인 연결을 확인합니다.
• 파이프 라인 연결 개수를 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs함수는 DFS + 그리드 알고리즘을 적용하여 격자 내에 파이프를 설치해봅니다.
• inSpace함수는 파이프를 연결할 공간이 격자 내에 존재하는지 확인합니다.

 

import java.io.*;
import java.util.*;

public class Main{
    static int R, C, answer = 0;
    static char[][] map;		// 격자 정보 배열
    static boolean[][] visited;		//방문 확인 배열
    static int[] dx = {1, 1, 1};	//파이프 연결 (↗, →, ↘) x 변경값
    static int[] dy = {-1, 0, 1};	//파이프 연결 (↗, →, ↘) y 변경값
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        visited = new boolean[R][C];
        //격자 정보 저장.
        for(int i=0;i<R;i++){
            String str = br.readLine();
            for(int j=0;j<C;j++)
                map[i][j] = str.charAt(j);
        }
        //위쪽부터 DFS 탐색 진행.
        for(int i=0;i<R;i++){
            visited[i][0] = true;
            if(dfs(i, 0))	//true : 파이프 라인 연결, false : 파이프 라인 실패
                answer++;
        }

        bw.write(answer + "");	//파이프 라인 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //DFS + 그리드 알고리즘으로 탐색하는 DFS 함수
    static boolean dfs(int y, int x){
        if(x==C-1)		//파이프 라인 연결 성공시!
            return true;

        //파이프 연결 탐색
        for(int i=0;i<3;i++){
            int tempX = x + dx[i];
            int tempY = y + dy[i];
            //파이프 연결 가능한 공간일 때
            if(inSpace(tempX, tempY) && !visited[tempY][tempX] && map[tempY][tempX]=='.'){
                visited[tempY][tempX] = true;
                if(dfs(tempY,tempX))	//파이프 연결하였을 때 파이프 라인 연결 성공시.
                    return true;
            }
        }
        return false;	//파이프 연결하였을 때 파이프 라인 연결 실패시
    }
    //다음 연결하려는 파이프가 격자내에 존재하는지 확인하는 배열
    static boolean inSpace(int x, int y){
        //격자 안에 존재할 때
        if(x>=0 && y>=0 && x<C && y<R)
            return true;
        return false;	//격자 안에 존재하지 않을 때
    }
}