[ 백준 9207 ] 페그 솔리테어 (C++)

# 문제링크

www.acmicpc.net/problem/9207

9207번: 페그 솔리테어

이 문제를 처음 봤을 때는 왜이렇게 어렵게 생각했는지 모르겠다. ㅎㅎㅎ 처음 봤을 때는 저 말들을 어떻게 움직여줘야하지? 그냥 무작위로 다 움직이면 되나? 저 말들의 위치값을 받아두어야 하나? 한 번 움직이면 그 다음은 어떡하지? ... 뭔가 정리가 안되었다. 그냥 for 문 돌면서 말의 위치를 찾아서, 말이 이동 가능한 모든 경우의 수로 돌려보면 되는 문제였다. 

 

근데 맵이 또 계속 달라지는데 어떻게 하지? 원본을 복사해뒀다가 한번 시뮬레이션을 하고 다시 돌려놔야 하나? 이런 생각을 했었다. 하,, 아직 내공이 많...~~~ 이 부족한 듯. 문제를 풀수록 내가 스스로 많이 부족하다는 걸 알기때문에 일요일에 있을 코딩테스트가 너무 너무 무섭다 ㅠㅠㅠ 문제 푸는걸 멈추면 더 불안하다.. 진짜 빨리 끝내야지 안그러면 사람 미칠거같다. 일요일에 꼭 붙어야하는데 ㅠㅠㅠㅠㅠㅠㅠ

 

암튼 다시 문제로 다시 돌아가서, 한 번 움직일 때마다 말이 하나씩 사라진다. 그래서 총 말의 개수에서 움직인 횟수를 빼주면, 남은 말의 수가 된다. 충격적인 사실.... 슥사 과정 알고리즘 강사님은 정말 천재이신거같다.. 

 

두가지 버전 코드를 올렸는데, 하나는 얍문님 블로그 보고 푼 코드이고, 아래쪽에는 강사님 설명 참고하여 작성한 코드이다.

 

# 제출 코드 

#include <cstdio>
using namespace std;

#define MAXH (5)
#define MAXW (9)
char map[MAXH + 2][MAXW + 2];
int solremain, solmove;
int N;

int xd[] = { 1, -1, 0,0 };
int yd[] = { 0, 0, 1, -1 };

void InputData() {
    N = 0;
    for (int h = 1; h <= MAXH; h++) {
        scanf("%s", &map[h][1]);
    }
}

int Check(char map[][11]) {
    int cnt = 0;
    for (int i = 1; i <= MAXH; i++) {
        for (int j = 1; j <= MAXW; j++) {
            if (map[i][j] == 'o') cnt++;
        }
    }
    return cnt;
}

void Copy_map(char a[][11], char b[][11]) {
    for (int i = 1; i <= MAXH; i++) {
        for (int j = 1; j <= MAXW; j++) {
            a[i][j] = b[i][j];
        }
    }
}
void DFS(int cnt, char map[][11]) {
    bool flag = false;
    char nmap[MAXH + 2][MAXW + 2];

    for (int i = 1; i <= MAXH; i++) {
        for (int j = 1; j <= MAXW; j++) {
            if (map[i][j] == 'o') {
                for (int k = 0; k < 4; k++) {
                    int ny = i + yd[k];
                    int nx = j + xd[k];

                    if (ny < 1 || ny > MAXH)continue;
                    if (nx < 1 || nx > MAXW)continue;
                    if (map[ny][nx] != 'o')continue;

                    int nny = ny + yd[k];
                    int nnx = nx + xd[k];

                    if (ny < 1 || ny > MAXH)continue;
                    if (nx < 1 || nx > MAXW)continue;
                    if (map[nny][nnx] != '.')continue;

                    flag = true;

                    Copy_map(nmap, map);
                    nmap[i][j] = '.';
                    nmap[ny][nx] = '.';
                    nmap[nny][nnx] = 'o';

                    DFS(cnt + 1, nmap);
                }
            }
        }
    }

    if (flag == false) { // 다 끝났니?.. ㄷㄷ
        int ret = Check(map);
        if (ret < solremain) {
            solremain = ret;
            solmove = cnt;
        }
        else if (ret == solremain) solmove > cnt ? cnt : solmove;
    }
}
int main() {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        InputData();//입력받는 부분

        solremain = 0x7fff, solmove = 0x7fffff;
        DFS(0, map);

        printf("%d %d\n", solremain, solmove);
    }
    return 0;
}

 

 

#include <stdio.h>
#define MAXH (5)
#define MAXW (9)
char map[MAXH + 2][MAXW + 2];
int solmove = 0x7fff;
int total;

void InputData(void) {
    for (int h = 1; h <= MAXH; h++) {
        scanf("%s", &map[h][1]);
        for (int j = 1; j <= MAXW; j++) {
            if (map[h][j] == 'o') total++;
        }
    }
}

int yd[] = { 1, -1, 0,0 };
int xd[] = { 0,0,1, -1 };

void DFS(int num) {
    if (num < solmove) solmove = num;
    for (int i = 1; i <= MAXH; i++) {
        for (int j = 1; j <= MAXW; j++) {
            if (map[i][j] == 'o') {

                for (int d = 0; d < 4; d++) {
                    int y = i + yd[d];
                    int x = j + xd[d];

                    if (x < 1 || x > MAXW) continue;
                    if (y <1 || y > MAXH)continue;
                    if (map[y][x] != 'o')continue;

                    int ny = y + yd[d];
                    int nx = x + xd[d];

                    if (nx < 1 || nx > MAXW) continue;
                    if (ny <1 || ny > MAXH)continue;
                    if (map[ny][nx] != '.')continue;

                    map[i][j] = '.';
                    map[y][x] = '.';
                    map[ny][nx] = 'o';

                    DFS(num - 1);

                    map[i][j] = 'o';
                    map[y][x] = 'o';
                    map[ny][nx] = '.';
                }

            }
        }
    }
}
void Init() {
    total = 0;
    solmove = 0x7fff;
}
int main(void) {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        Init();

        InputData();

        DFS(total);

        printf("%d %d\n", solmove, total - solmove);
    }
    return 0;
}