(Baekjoon) GreedyAlgorithm - (24) 빵집

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

3109번: 빵집

1. 1열에서 시작해서 마지막열까지 간다.

2. 대각선 위, 오른쪽, 대각선 아래로 이동가능하다.

3. 최대한 여러개를 설치해야한다.

4. 경로는 절대 겹쳐질수없다.

5. 첫째열과 마지막열은 항상 비어있다.

6. 최대 개수를 구하는것이다.

7. R과 C가 주어지며 R은 행 C는 열이다.

8. R(1 ~ 10000), C(5 ~ 500)

 

 

package GreedyAlgorithm;

import java.util.Scanner;

public class _3109 {

    static int row;
    static int column;
    static char Gas_RouteMap[][];
    static int Count_GasRount = 0;
    public static void main(String args[]) {

        Scanner inputscanner = new Scanner(System.in);
        row = inputscanner.nextInt();
        column = inputscanner.nextInt();
        Gas_RouteMap = new char[row][column];

        String TempforChar;
        for (int i = 0; i < row; i++) {
            TempforChar = inputscanner.next();
            for (int j = 0; j < column; j++) 
                Gas_RouteMap[i][j] = TempforChar.charAt(j);
        }

        for (int Track = 0; Track < row; Track++) 
            SearchingGasRoute_Backtracking(Track,0);

        inputscanner.close();

        System.out.println(Count_GasRount);

    }

    static boolean SearchingGasRoute_Backtracking(int Track, int Goal) {

        Gas_RouteMap[Track][Goal] = 'x';

        if(Goal == column - 1){
            Count_GasRount++;
            return true;
        }
        
        if( ( (Track-1) >=  0  )  && ( (Goal+1) < column ) && ( Gas_RouteMap[Track-1][Goal+1] == '.' ))
            if(SearchingGasRoute_Backtracking(Track-1,Goal+1) == true)
                return true;
        if( ( (Goal+1) < column ) && ( Gas_RouteMap[Track][Goal+1] == '.' ) )
            if(SearchingGasRoute_Backtracking(Track,Goal+1) == true)
                return true;
        if( ( (Track+1) < row )  && ( (Goal+1) < column ) && ( Gas_RouteMap[Track+1][Goal+1] == '.' ))
            if(SearchingGasRoute_Backtracking(Track+1,Goal+1) == true)
                return true;

        Gas_RouteMap[Track][Goal] = '.';
        
        return false;
    }


    
}

 

위와 같이 DFS탐색을 사용하여서 풀이하였으나 시간초과가 뜨게 되었다.

예상은 했지만 생각보다 많은걸 검색해야 했나보다.

 

그리디알고리즘인 만큼 생각없이 무조건 DFS의 의존하라고 출제하지는 않았을것이다. 다른방법을 생각해야겠다.

한 두시간을 고민한끝에 그냥 다른사람 풀이를 보았다.

 

하지만 내가 크게 실수한건 아니였단걸 깨달았다. 내 방법이 맞았으나 dp를 사용하지 않았던것이 실수였다.

내가 한 방법은 시도했던길은 x를 표시로 하고 성공하지 못한단면 다시 . 으로 바꾸는것이였는데

이것을 . 으로 바꾸지 않을경우 dp와 비슷한 효과를 내었다.

원상복귀를 할 필요없이 그냥 지나갔다는 표시로 x로 남겨두면 된다.

 

결과적으로 위의 코드에서 코드 한줄만 삭제하면된다.

 

 

 

결과적으로 코드는 다음과 같다.

package GreedyAlgorithm;

import java.util.Scanner;

public class _3109 {

    static int row;
    static int column;
    static char Gas_RouteMap[][];
    static int Count_GasRount = 0;
    public static void main(String args[]) {

        Scanner inputscanner = new Scanner(System.in);
        row = inputscanner.nextInt();
        column = inputscanner.nextInt();
        Gas_RouteMap = new char[row][column];

        String TempforChar;
        for (int i = 0; i < row; i++) {
            TempforChar = inputscanner.next();
            for (int j = 0; j < column; j++) 
                Gas_RouteMap[i][j] = TempforChar.charAt(j);
        }

        for (int Track = 0; Track < row; Track++)
            SearchingGasRoute_Backtracking(Track,0);

        inputscanner.close();

        System.out.println(Count_GasRount);

    }

    static boolean SearchingGasRoute_Backtracking(int Track, int Goal) {

        Gas_RouteMap[Track][Goal] = 'x';

        if(Goal == column - 1){
            Count_GasRount++;
            return true;
        }
        
        if( ( (Track-1) >=  0  )  && ( (Goal+1) < column ) && ( Gas_RouteMap[Track-1][Goal+1] == '.' ))
            if(SearchingGasRoute_Backtracking(Track-1,Goal+1) == true)
                return true;
        if( ( (Goal+1) < column ) && ( Gas_RouteMap[Track][Goal+1] == '.' ) )
            if(SearchingGasRoute_Backtracking(Track,Goal+1) == true)
                return true;
        if( ( (Track+1) < row )  && ( (Goal+1) < column ) && ( Gas_RouteMap[Track+1][Goal+1] == '.' ))
            if(SearchingGasRoute_Backtracking(Track+1,Goal+1) == true)
                return true;
                
        return false;
    }


    
}

 

코드 한줄의 영향력이 이렇게 클줄이야... 다음부턴 개념을 더 확실히 알고 진행해야겠다.

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study