[틀림] 백준 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;
}

 

* 2회독

• 조합 코드는 잘 외웠음.

combi(-1,0); //시작
void combi(int idx, vector<int> & v) {
   if(v.size()==7) {
      // for(auto i : v ) {
      //    cout<<i<<" ";
      // }cout<<"\n";
      go(v);
      return;
   }
   for(int i=idx+1;i<25;++i) {
      v.push_back(i);
      combi(i,v);
      v.pop_back();
   }
}

• 좌표변환은 x의 size로 / % 한게 2차원 좌표임

• 인접검사방법
  • 뽑은 조합을 selected 배열에 기록
  • int dfs로 connected component의 갯수 세기
    • 이떄, selected가 아니면 continue!
    • 리턴값이 7이면 모두 인접한것임.
• 비효율적 인접검사 방법
  • 뽑은 조합을 selected 배열에 기록
  • void dfs 돌리기(vis에 기록)
  • vis와 selected가 똑같은지 검사

//비효율적 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char a[5][5];
int ret, vis1[5][5],vis2[5][5];//방문해야할곳, 방문한곳
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};

void dfs(int y, int x) {
   vis2[y][x]=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 (vis2[ny][nx]) continue;
      if(vis1[ny][nx]==0) continue; //!!!방문해야할곳이 아니면 패스!!!
      dfs(ny,nx);
   }
}

void go(vector<int> & v) {

   memset(vis1,0,sizeof(vis1));
   memset(vis2,0,sizeof(vis2));
   
   int cnt=0;//S갯수
   for(auto i : v) {
      int y = i/5;
      int x = i%5;

      vis1[y][x]=1;
      if(a[y][x]=='S') cnt++;
   }
   dfs(v[0]/5,v[0]%5);

   int adj=1;
   for(int i=0;i<5;++i) {
      for(int j=0;j<5;++j) {
         if(vis1[i][j]!=vis2[i][j]) {
            adj=0;
            break;
         }
      }
      if(!adj) break;
   }
   if(adj && cnt>=4) ret++;
}

void combi(int idx, vector<int> & v) {
   if(v.size()==7) {
      // for(auto i : v ) {
      //    cout<<i<<" ";
      // }cout<<"\n";
      go(v);
      return;
   }
   for(int i=idx+1;i<25;++i) {
      v.push_back(i);
      combi(i,v);
      v.pop_back();
   }
}
int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

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

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

   vector<int> v;
   combi(-1,v);
   
   cout<<ret;
   
   return 0;
}

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

char a[5][5];
int ret, vis1[5][5],vis2[5][5];//방문해야할곳, 방문한곳
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};

void dfs(int y, int x) {
   vis2[y][x]=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 (vis2[ny][nx]) continue;
      if(vis1[ny][nx]==0) continue; //!!!방문해야할곳이 아니면 패스!!!
      dfs(ny,nx);
   }
}

int dfs2(int y, int x) {
   vis2[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 (vis2[ny][nx]) continue;
      if(vis1[ny][nx]==0) continue; //!!!방문해야할곳이 아니면 패스!!!
      ret += dfs2(ny,nx);
   }
   return ret;
}

void go(vector<int> & v) {

   memset(vis1,0,sizeof(vis1));
   memset(vis2,0,sizeof(vis2));
   
   int cnt=0;//S갯수
   for(auto i : v) {
      int y = i/5;
      int x = i%5;

      vis1[y][x]=1;
      if(a[y][x]=='S') cnt++;
   }
   int cnt2=dfs2(v[0]/5,v[0]%5);
   
   if(cnt2==7 && cnt>=4) ret++;
}

void combi(int idx, vector<int> & v) {
   if(v.size()==7) {
      // for(auto i : v ) {
      //    cout<<i<<" ";
      // }cout<<"\n";
      go(v);
      return;
   }
   for(int i=idx+1;i<25;++i) {
      v.push_back(i);
      combi(i,v);
      v.pop_back();
   }
}
int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

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

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

   vector<int> v;
   combi(-1,v);
   
   cout<<ret;
   
   return 0;
}