[BOJ 1941] 소문난 칠공주

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

 

2차원 배열에서 연속된 것을 구한다는 점에서 bfs나 dfs로 구할 수 있을 것같다.

그러나 BFS와 DFS는 뻗어나가는 형식이기 때문에 이런 규칙이 적용되지 않는 경우는 찾기 힘들다.

 

그래서 이번 문제는 단순히 이차원 배열에서 인접한 것만 찾는 방법 대신

S가 Y보다 큰 조합을 뽑은 다음, 서로 인접해있는지 체크하는 방법을 사용해야한다.

 

따라서 이중 for문을 통해 이차원 탐색을 하는 대신, 일차원 배열에서 가능성있는지 탐구한다.예를 들어, 1번째 사람이 올 수 있는지 -> 2번째 사람이 올 수 있는지 -> ... -> 25번째 사람이 올 수 있는지이 과정에서 백트래킹을 이용해 여러 조합들을 뽑을 수 있다.

 

그렇기 때문에 아래와 같이 일차원 배열에서 x와 y를 뽑아서 사용한다.

 

/* 잘못된 코드 */

for (int i = x; i < 5;i++) {
	for(int j = y; j < 5; j++){
		if (!visited[i]) {
			int x = i
			int y = j

			// 이하 생략
		}
    }		
}

/* 수정된 코드 */

for (int i = idx; i < 25;i++) {

	int x = i / 5;
	int y = i % 5;

	// 이하 생략
}

 

---

DFS를 사용한 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int n, m;
char arr[5][5];
bool visited[26];
int pos_x[4] = { 0,0,1,-1 };
int pos_y[4] = { 1,-1,0,0 };
queue<pair<int,int>> q;
vector<pair<int, int>> v;
int s_cnt = 0;
int tot_cnt = 0;
int res = 0;

// 인접한지 체크하는 함수
/*
	1. 저장한 7개의 원소를 for문으로 돌린다.
    2. 상하좌우로 인접하면, 해당 좌표를 큐에 넣는다.
    3. 큐에서 하나를 빼서 다시 상하좌우로 인접한지 체크
    4. 체크한 갯수가 7개가 되면 true를 반환
*/
bool check() {
	queue<pair<int,int>> q;
	q.push(v[0]);
	bool chk[8] = { false, };
	chk[0] = true;
	int cnt = 0;

	while (!q.empty()) {
		pair<int, int> cur;
		cur = q.front();

		q.pop();
		for (int i = 1; i < 7; i++) {
			if (chk[i])	continue;
			for (int j = 0; j < 4; j++) {
				int nx = cur.first + pos_x[j];
				int ny = cur.second + pos_y[j];
				if (nx == v[i].first && ny == v[i].second) {
					q.push({ nx,ny });
					chk[i] = true;
					cnt++;
				}
			}
		}
	}
	if (cnt == 6)	return true;
	else return false;
}

void bfs(int idx, int s_cnt,int y_cnt) {
	
	if (s_cnt + y_cnt == 7) {
		
		if (s_cnt>y_cnt) {
			if(check()==true)
			tot_cnt++;
		}
		return;
	}
	for (int i = idx; i < 25;i++) {
		

		if (!visited[i]) {
			int x = i / 5;
			int y = i % 5;

			v.push_back({ x,y });
			visited[i] = true;
			if (arr[x][y] == 'S')
				bfs(i + 1, s_cnt+1,y_cnt);
			else
				bfs(i + 1, s_cnt, y_cnt+1);
			visited[i] = false;
			v.pop_back();
		}
		
	}
	
}

int main() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			scanf("%c", &arr[i][j]);
		}
		getchar();
	}
	bfs(0, 0, 0);
	cout << tot_cnt;
}

---

 

참고: https://imnotabear.tistory.com/178