이코테, 백준 - 18428

문제

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

18428번: 감시 피하기

dfs를 이용해 장애물 설치의 모든 경우의 수를 다 해보고 감시를 피할 수 있는지 확인하는 문제였다. (백트래킹)

 

---

문제 풀이

처음에는 빈 칸의 좌표를 따로 저장하지 않고, 상하좌우로만 이동하며 장애물을 설치했는데 비효율적인 것 같아서 빈 칸의 좌표를 map 입력받을 때 같이 저장해줬다. 그리고 엄청난 실수를 했는데, dfs에서 count+1과 i+1을 넘겨줘야 했는데 count+1과 인자로 받은 index+1을 넘겨줘서 헤맸다.. 당연히 i+1로 넘겨줬겠지 하고 그 부분이 틀렸다는 생각조차 못하고 다른 부분에 문제가 있는줄 알고 계속 고쳤다. printMap으로 count가 3이 되어 check할 때마다 map을 찍었을 때 분명 장애물이 2개, 1개인데 count 조건을 만족해서... 뭔일인가 했더니 index+1의 문제....

 

사소하지만 찾기 어려운 실수를 빨리 찾아낼 수 있도록 노력해야 할 것 같다. 이런 실수를 안하면 참 좋을텐데 ^^

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <queue>

using namespace std;

int N;
char map[6][6] = { 0 }; //T,S,O,X
int tnum = 0; //선생님 수
int dx[4] = {1, -1, 0, 0};
int dy[4] = { 0, 0,1,-1 };
int flag = 0;
vector<pair<int, int>> e,t; //빈 칸 위치
int emptyNum; //빈 칸 개수

void printMap() {
    int i, j;

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%c ", map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

bool isThereStudent(int x,int y) {
    int i;
    int nx, ny;

    for (i = 0; i < 4; i++) { //4방향 확인
        nx = x;
        ny = y;
        while (nx >= 0 && nx < N && ny >= 0 && ny < N) {
            if (map[nx][ny] == 'O') //장애물 있으면 멈추기
                break;
            if (map[nx][ny] == 'S') { //학생 있음
                return true;
            }
            nx += dx[i];
            ny += dy[i];
        }
    }
    return false;
}

bool chekcAllTeacher() {
    int i;

    for (i = 0; i < tnum; i++) {
        if (isThereStudent(t[i].first, t[i].second)) { //학생 발견
            return false;
        }
    }
    return true; //통과
}

void dfs(int cnt, int index) {
    int i;

    if (cnt == 3) { //장애물 설치 완료
        if (chekcAllTeacher()) {
            printf("YES");
            exit(0);
        }        
        return;
    }    

    for (i = index; i < emptyNum; i++) {
        map[e[i].first][e[i].second] = 'O';
        dfs(cnt + 1, i+1);
        map[e[i].first][e[i].second] = 'X';
    }

}

int main() {  
   
    int i, j;

    scanf("%d", &N);

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            getchar();
            scanf("%c", &map[i][j]);            
            if (map[i][j] == 'T')
                t.push_back(make_pair(i, j));                                            
            else if(map[i][j] == 'X')
                e.push_back(make_pair(i, j));            
        }
    }
    emptyNum = e.size();
    tnum = t.size();

    dfs(0, 0);

    printf("NO");

    return 0;
}

/*
5
X S X X T
T X S X X
X X X X X
X T X X X
X X T X X

4
S S S T
X X X X
X X X X
T T T X

5
X X S X X
X X X X X
S X T X S
X X X X X
X X S X X

5
X T X T X
T X S X T
X S S S X
T X S X X
X T X X X
*/