백준 9207번 페그 솔리테어

문제 링크입니다: https://www.acmicpc.net/problem/9207

재미있는 브루트 포스(Brute Force), 백트래킹 문제였습니다.

알고리즘은 아래와 같습니다.

1. o의 개수를 무한대로 초기화하고 DFS 함수를 호출합니다.

2. 모든 칸을 살피며 o를 찾고 해당 o의 인접한 칸에 또 o가 있고 인접한 칸의 다음 칸이 비어있다면 문제의 규칙에 따라 인접한 칸의 o를 제거하고 비어있는 칸으로 이동한 뒤 DFS 함수를 또 재귀 호출합니다.

3. 모든 칸을 살폈는데도 움직일 o가 없다면 더 이상 진행할 수 없으므로 현재 보드에 있는 o의 개수를 세고 o의 개수와 최소횟수를 업데이트 해줍니다.

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int o, result;

string board[5];

 

void DFS(int cnt, string s[5])

{

        bool flag = false;

        string copyBoard[5];

 

        for (int j = 0; j < 5; j++)

        {

                 for (int k = 0; k < 9; k++)

                 {

                         //o이고

                         if (s[j][k] == 'o')

                         {

                                 for (int i = 0; i < 4; i++)

                                 {

                                          int nextY = j + moveDir[i].y;

                                          int nextX = k + moveDir[i].x;

                                          int nextYY = j + 2 * moveDir[i].y;

                                          int nextXX = k + 2 * moveDir[i].x;

 

                                          //인접한 칸도 o이고 인접한 칸의 다음칸은 비어있다면

                                          if (0 <= nextYY && nextYY < 5 && 0 <= nextXX && nextXX < 9)

                                                  if (s[nextY][nextX] == 'o' && s[nextYY][nextXX] == '.')

                                                  {

                                                          flag = true;

                                                          for (int l = 0; l < 5; l++)

                                                                   copyBoard[l] = s[l];

                                                          copyBoard[j][k] = '.';

                                                          copyBoard[nextY][nextX] = '.';

                                                          copyBoard[nextYY][nextXX] = 'o';

                                                          DFS(cnt + 1, copyBoard);

                                                  }

                                 }

                         }

                 }

        }

 

        //o를 하나도 못 움직였다면 더 이상 진행 불가

        if (!flag)

        {

                 int num = 0;

                 for (int i = 0; i < 5; i++)

                         for (int j = 0; j < 9; j++)

                                 if (s[i][j] == 'o')

                                          num++;

 

                 if (o > num) //o의 개수를 업데이트하며 횟수도 업데이트

                 {

                         o = num;

                         result = cnt;

                 }

                 //o의 개수는 같지만 횟수가 더 적을 때 최소 횟수 업데이트

                 else if (o == num && result > cnt)

                         result = cnt;

        }

        return;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        for (int t = 0; t < N; t++)

        {

                 for (int i = 0; i < 5; i++)

                         cin >> board[i];

 

                 o = INF;

                 DFS(0, board);

                 cout << o << " " << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~