빵집(백준_3109)

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

3109번: 빵집

 

문제 설명

문제가  길지만 간단하게 설명하자면 예제 입력에 있는 5 *  5 이차원 배열에서 1열에서 5열까지 파이프를 연결해야 한다. 그 때 X에는 연결 할 수 없고 한 곳에는 하나의 파이프만 지나갈 수 있다. 그리고 파이프를 설치할 수 있는 곳은 현재를 기준으로 오른쪽 위, 오른쪽, 오른쪽 아래 이렇게 3개이다.

이 때 파이프를 설치할 수 있는 최대 개수를 구하는 프로그램이다.

예제를 직접 풀어보면 이렇게 2개 파이프를 연결할 수 있다.

 

문제에 대한 아이디어

매 순간 최선의 선택을 해야하는 그리디 알고리즘을 써서 풀 수 있는 문제이다.

1열에서 마지막열 까지 X를 만나지 않고 가야 한다. 

최선의 선택이 어떤 것인지 기준을 잡으면 쉽게 풀 수 있다.  혼자 풀다가 틀려서 구글링을 해서 기준을 잡아 봤다.

 

지나가는 곳은 파이프가 지나 갔으므로 - 로 바꾼다. 

• 최고로 많이 파이프를 연결할려면 제일 위에서 시작한 것은 마지막 도착할 때도 제일 위에 도착하는 것이 좋다.
• 첫번째 행이 아니면 무조건 오른쪽 위로 올라가는 것부터 시작한다. 
• 그 다음 오른쪽으로 가는 것을 실행한다.
• 그 다음 오른쪽 아래로 가는 것을 실행한다.

한 칸에는 하나의 파이프만 지나갈 수 있으므로 도착을 성공한 파이프는 안 지워도 된다.

실패한 파이프도 안 지워도 된다.
왜냐 하면 어차피 그 파이프는 실패한 파이프이기 때문에 그 파이프 방향으로 다시가면 실패할 것이다.
지우지 않아야 실패할 것을 더 빨리 알 수 있다.

 

구현

• Main

public static void main(String[] args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(buf.readLine());
    R = Integer.parseInt(st.nextToken()); // 가로행의 크기
    C = Integer.parseInt(st.nextToken()); // 세로열의 크기
    pro = new char[R][C];
    for(int i =0; i<R; ++i){
        pro[i] = buf.readLine().toCharArray(); 
    }
    int result = 0;
    for(int i =0; i<R; ++i){
        if(check(i,0)) ++result; // check를 통해 파이프 연결을 성공하면 하나씩 카운트롤 높인다.
    }
    System.out.println(result);
}

• Check

public static boolean check(int y, int x){
    pro[y][x] = '-'; // 지나간 곳은 파이프가 갔다고 표시
    
    //마지막 열에 도착했으면 true 리턴
    if(x == C-1){ 
        return true;
    }
    
     //오른쪽 위 방향
    if(y > 0 && pro[y-1][x+1] == '.') {
        if(check(y-1, x+1))
           return true;
    }
    
    // 오른쪽 방향
    if(pro[y][x+1] == '.') {
        if(check(y,x+1)) 
            return true;
    }
    
     // 오른쪽 아래 방향
    if(y < R-1 && pro[y+1][x+1] == '.') {
        if(check(y+1,x+1))
            return true;
    }
    
    //모든 방향으로 가지 못하면 false 리턴 
    return false;
}

check를 검사하는 파이프를 설치하러 갔다가 실패하고 return 될 경우 false이면 모든 return이 false여야 하기 때문에 

if(check) return true를 추가해 주었다.

 

https://github.com/Heron-Woong/CodingTest_Practice/commit/476ec10375a36770d69f008ccde98cf60c9d6c6e

백준_3109, 빵집 · Heron-Woong/CodingTest_Practice@476ec10