백준 1941 소문난 칠공주 c++ // 1차원배열을 2차원좌표로 매핑하는법 , 백트래킹, dfs

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

1941번: 소문난 칠공주

1. 1차원배열을 2차원좌표로 매핑하는법 

1차원 idx : 0 1 2 3 4 5 6 7 8 9 ...... 24

2차원 : (0,0) (0,1) ....               (4,4)

y좌표 == 1차원idx /5

x좌표 == 1차원 idx %5 하면 된다!

 

 

2. 풀이과정

1. 25C7로 인덱스를 조합한다. (방문할 대상들의 좌표를 조합)

2. idx로 배열에 접근 후 , s_cnt>=4인지 검사

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

3. 방문할 대상을 v에 체크

4. dfs 돌면서 실제 방문한곳을 visited에 체크

5. v(방문해야할곳)과 visited(방문한곳)이 같으면 모두 인접한것임.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

6. s4명이상 && 모두 인접 -> ret++

 

3. 시간복잡도

25C7(480700) * ( 7(for) + 7(dfs) +25(2중for)) == 약 1800만

1억 이하이므로 -> 가능하다

 

4. 전체코드

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

char a[5][5];
int v[5][5],ny, nx, ret,arr[25], isused[25],visited[5][5];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};



void dfs(int y, int x) {
	visited[y][x] = 1;


	for (int i = 0; i < 4; ++i) {
		ny = y + dy[i];
		nx = x + dx[i];
		if (ny < 0 || ny >= 5 || nx < 0 || nx >= 5) continue;
		if (visited[ny][nx]) continue;
		if (v[ny][nx] == 0) continue;	//방문대상이 아니면 pass
		
		dfs(ny, nx);
	}
	return;

}

//현재까지 k개 뽑음
//25C7 구현
//i = 0 ~ 24 
// n/5==y좌표 , n%5==x좌표로 사용하면 된다,
void go(int k) {
	if (k >= 7) {
		fill(&v[0][0], &v[0][0] + 5 * 5, 0);
		fill(&visited[0][0], &visited[0][0] + 5 * 5, 0);

		int y_cnt=0;
		int s_cnt = 0;
		for (int i = 0; i < 7; ++i) {
			//cout << arr[i] << " ";
			int y = arr[i] / 5;
			int x = arr[i] % 5;

			v[y][x] = 1;	//방문해야할곳 체크

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

		}
		bool s_many = false;
		if (s_cnt >= 4) s_many = true;

		/////////////////////////////////////
		dfs(arr[0] / 5, arr[0] % 5);

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

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

		bool all_adj = true;
		for (int i = 0; i < 5; ++i) {
			for (int j = 0; j < 5; ++j) {
				if (visited[i][j] != v[i][j]) {
					all_adj = false;
					break;
				}
			}
		}		

		//cout << s_many << " " << all_adj<<"\n";
		if (s_many && all_adj) ret++;
		//cout << "\n";
		return;
	}

	int st = 0;
	if (k != 0) st = arr[k - 1]+1;

	for (int i = st; i < 25; ++i) {
		if (isused[i]) continue;
		arr[k] = i;
		isused[i] = 1;
		go(k + 1);
		isused[i] = 0;
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 5; ++i) {
		string temp;
		cin >> temp;
		for (int j = 0; j < 5; ++j) {
			a[i][j]= temp[j];
		}
	}

	go(0);




	cout << ret;
}