[BaekJoon] 1941 소문난 칠공주 :: monton

문제

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

풀기

이 문제는 dfs를 사용하여 풀수 있는 문제이다

맨 처음 어떻게 풀어야 할지 감이 안와서 다른 분들의 코드를 참고 했는데 7개의 위치를 먼저 뽑는 것이다

이렇게 하는 이유는 dfs를 사용해야 하는데 dfs는 'ㅓ','ㅗ','ㅜ','ㅏ' 과 같은 모양은 탐색을 할 수 없기 때문에

모든 경우의 수를 다 돌아야 한다

일단 총 25개 중에서 7개를 뽑아야 한다. 그리고 인덱스는 행은  i/25, 열은 i%25 로 잡아주면 된다

그렇게 7개를 잡아주고 이 7개가 서로 연결되어 있는지 확인해준다

총 dfs를 두번 사용하였는데 1. 7개 수 모두 뽑기 2. 연결 되었는지 확인하기 로 두가지로 기능이 나뉜다

아이디어 생각하기가 어려워서 그렇지 코딩은 어렵지 않았다

재밌는 문제였던거 같다

코드

#include<iostream>
#include<queue>
using namespace std;
 
char arr[6][6];
int visit[26],map[6][6],chkmap[6][6],flag,ans;
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
void init() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            map[i][j] = chkmap[i][j] = 0;
        }
    }
}
 
int chkvisit() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (map[i][j] && !chkmap[i][j]) return 0;
        }
    }
 
    return 1;
}
 
void chkconn(int x, int y,int cnt) {
    if (chkvisit()) {
        flag = 1;
        return;
    }
 
    if (x < 0 || y < 0 || x >= 5 || y >= 5) return;
    if (!map[x][y]||chkmap[x][y]) return;
 
    chkmap[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        chkconn(x + dir[i][0], y + dir[i][1],cnt+1);
    }
}
 
void dfs(int x,int cnt) {
    if (cnt == 7) {
        init();
        int n = 0;
        for (int j = 0; j < 25; j++) if (visit[j]&&arr[j / 5][j % 5] == 'S') n++;
        if (n < 4) return;
 
        for (int j = 0; j < 25; j++) if (visit[j]) map[j / 5][j % 5] = 1;
        
        flag = 0;
        for (int j = 0; j < 25; j++) 
            if (visit[j]) {
                chkconn(j / 5, j % 5,0);
                break;
            }
 
        if (flag) {
            ans++;
        }
        return;
    }
 
    for (int i = x; i < 25; i++) {
        if (!visit[i]) {
            visit[i] = 1;
            dfs(i, cnt + 1);
            visit[i] = 0;
        }
    }
}
 
int main() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> arr[i][j];
        }
    }
 
    dfs(0, 0);
    printf("%d\n", ans);
}