[BaekJoon/백준] 9207번 페그 솔리테어

 

어떻게 풀지.. 하고 한시간 고민했다가 접근 방법을 찾아봤다.

 

간단하게 백트래킹으로 풀 수 있는 문제였다.

 

백트래킹이란, 내가 DFS의 활용에는 두 가지가 있다고 했었는데, 그 중 토글형 방식에 속한다.

"선택해서 진행하고, 이전 상태로 되돌아오는 방식". stack 느낌으로 진행되는 방식이다.

( A = true; DFS(); A = false; 형식)

 

갈때까지 가며 DFS 해주면서, 토글을 통해 백트래킹(다시 되돌아가는)하고 또 진행하고..!

/*
 백트래킹(DFS 토글형) 문제였다.
 갈때까지 가면서 진행해준다.
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T;

char MAP[5][9];


int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};

vector<pair<int, int>> result;

int COMP(pair<int, int> a, pair<int, int> b) {
    
    if(a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
    
}

void DFS(int DEPTH) {
    
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 9; j++) {
            
            if(MAP[i][j] == 'o') {
        
                
                for(int k = 0; k < 4; k++) {
                    
                    int tx = i + mx[k];
                    int ty = j + my[k];
                    
                    if(tx < 0 || tx >= 5 || ty < 0 || ty >= 9)
                        continue;
                    
                    int ttx = tx + mx[k];
                    int tty = ty + my[k];
                    
                    
                    if(ttx < 0 || ttx >= 5 || tty < 0 || tty >= 9)
                        continue;
                    
                    if(MAP[tx][ty] == 'o' && MAP[ttx][tty] == '.') { // 움직일 수 있음.
                        
                        MAP[i][j] = '.';
                        MAP[tx][ty] = '.';
                        MAP[ttx][tty] = 'o';
                                                
                        DFS(DEPTH + 1);
                        
                        
                        MAP[i][j] = 'o';
                        MAP[tx][ty] = 'o';
                        MAP[ttx][tty] = '.';

                        
                    }
                    
                }

            }
            

        }
                
        
    }
    
    
    int CNT = 0;
    
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 9; j++) {
            if(MAP[i][j] == 'o') {
                CNT++;
            }
        }
    }

    result.push_back({CNT, DEPTH});
}

int main() {
    
    cin >> T;
    
    while(T--) {
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 9; j++) {
                cin >> MAP[i][j];
                
            }
        }
        

        result.clear();
        
        DFS(0);

        
        sort(result.begin(), result.end(), COMP);
        
        
        cout << result[0].first << " " << result[0].second << "\n";
    }
    
}

 

소요 시간 : 1시간 40분