[Algo] 백준 소문난칠공주 c++ // 조합, 완탐, 갯수세기는 int dfs

• 일단 이문제는 2번째 푸는  문제이다.
• 근데 못풀었다...
• 모 기업 코테에서 비슷한 문제가 나와 다시 복습하였다.

 

* 못푼이유

• 설계도가 없으니 중간에 막히면 코드만 수정함 -> 점점 스파게티가 되어 망하였다.
•  아래정도 설계는 꼭하자!

* 의사코드

• 25C7 구현
  • vector를 넥퍼돌리면서 1인부분의 idx를 selected에 넣으면된다.
  • 이때, 지도에도 표시해둔다. //나중에 선택된곳만 갈수있도록 제한해야하니까.
  • i/5, i%5를 이용해, 값을 2차원으로 바꿔준다.

• 이다솜 cnt > = 4 구현
  • selected를 순회하면서 arr을 검사한다.
  • 이후 4이상인 경우만 dfs 검사로 보낸다.
  • 이때, selected 중 아무 좌표나 하나 보내면 된다.

임의의 좌표 하나에서 dfs 시작하면됨

• dfs 구현 - version 1
  • dfs는 연결된 갯수가 7개이면, 정답을 +1 하면된다.
  • 처음에 오답을 냈는데, 그 이유는 다음과같다.
  • 처음 dfs 설계는 매개변수에 cnt를 두고 다음 dfs로 갈때 +1 하는 방식이었다.
  • 이방식의 문제는 다음과 같다.
  • 백트랙이 필요한경우, 파란색글씨 부분으로 들어갈때 기존의 2에서 +1 되면서 의도와 다르게 동작하는 것으로 추측된다.

여기서 설계도를 그린 효과가 나타난다. / 설계도를 보면서 선택된 곳만 갈수있도록 코드를 수정했다.

• gpt 탐색결과 매개변수로 O 갯수를 세려면
  • int & count를 이용하고, 처음에서 count++ 해줘도 된다!

// DFS를 사용하여 연결성 검사
void dfs(int x, int y, int& count) {
    visited[x * N + y] = true;
    count++;

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx * N + ny] && (selected[nx * N + ny] == 1)) {
            dfs(nx, ny, count);
        }
    }
}

 

 

• dfs 구현 - version2
  • int dfs를 이용해, 제대로 구현했다.
  • 여기서 중요한점은, ret=1로 두고, ret+=dfs()이 코드이다.
  • 이 원리를 이해하는게 중요하다. 1(초기 ret값) + 모든자식노드의 ret값. 이 합쳐져서 최종 O 갯수가 리턴된다. 

 

* 결론

• O 갯수 세기는 int dfs를 사용하라. // cnt 매개변수 사용금지!
• 조합 + dfs 문제는 단골이므로 나만의 패턴을 만들자.
•  

조합용 벡터 만들기

초기화 부분은 do 문에서 처리

dfs도 방문처리 , ret값 설정위치 기억. (첫줄에 하면됨)

 

 

* 전체코드

#include <bits/stdc++.h>
using namespace std;

char a[5][5];

int vis[5][5], sel[5][5];
int ret,n;
vector<int> selected;

int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };

int dfs(int y, int x);


void go() {
    int s_cnt = 0; //이다솜파 학생수
    int y, x;
    for (auto i : selected) {
        y = i / 5;
        x = i % 5;

        if (a[y][x] == 'S') s_cnt++;
    }

    //cout << selected.size() << " ";
    //4개 이상인경우, 인접검사통과하면 정답++
    if (s_cnt >= 4) {
        //cout << "hello";
        if (dfs(y, x) == 7) //뽑은 7개중 아무데서나 시작해도됨
            ret++;
    }
}

//연결된 학생수 저장해야함
int dfs(int y, int x) {
    //if (connect_cnt == 7) {
    //    //ret++;
    //    return;
    //}
    vis[y][x] = 1;
    int ret = 1;

    for (int i = 0; i < 4; ++i) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || ny >= 5 || nx < 0 || nx >= 5) continue;
        if (vis[ny][nx]) continue;
        if (!sel[ny][nx]) continue; //선택된곳이 아니면 갈수없음!
        
        ret += dfs(ny, nx);
    }
    return ret;
}
int main()
{
    for (int i = 0; i < 5; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < 5; ++j) {

            a[i][j] = s[j];
        }
    }

  /*  for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            cout << a[i][j];
        }
        cout << "\n";
    }*/

   /* for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            memset(vis, 0, sizeof(vis));
            dfs(i, j, 0, "");
        }
    }*/

    //25C7 구현
    // N개의 요소를 가진 벡터 생성, 뒤에서 K개만 1로 설정
    n = 25;
    vector<int> v(n);
    fill(v.end() - 7, v.end(), 1);

    int cnt = 0;
    do {
        cnt++;
        selected.clear();
        memset(vis, 0, sizeof(vis));
        memset(sel, 0, sizeof(sel));
        for (int i = 0; i < 25; ++i) {
            if (v[i]) {
                selected.push_back(i);
                sel[i / 5][i % 5] = 1; //선택된 사람들
            }
        }
        //cout << "\n";

        go();
        
    } while (next_permutation(v.begin(), v.end()));
    
    cout << ret;
    


    return 0;
}