[백준 18428] 감시 피하기 c++ (완전 탐색)

 

문제 링크

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

18428번: 감시 피하기

 

문제 해설

N의 크기가 6으로, 전체 탐색이 6*6=36밖에 안되고, 장애물의 개수 역시 3개로 고정값이다.

따라서 permutation을 구현하여  장애물을 배정할 임의의 3개의 장애물의 위치를 정하고, 해당 위치에서 모든 학생이 걸리지 않는가? 를 테스트하는 방식으로 구현했다. 

정답 코드

#include<iostream>
#include<vector>
using namespace std;
char arr[6][6];
int obj_num = 3;
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
int N;
bool answer = false;
vector<pair<int, int>> stu;
vector<pair<int, int>> teach;
bool chk;
int cnt = 0;
bool isValid() {
	for (int i = 0; i < teach.size(); i++) {
		int t_r = teach[i].first, t_c = teach[i].second;
		for (int d = 0; d < 4; d++) {
			int nr = t_r + dr[d], nc = t_c + dc[d];
			while ((0 <=nr && nr <N && 0 <= nc && nc < N) &&arr[nr][nc]!='O') {
				if (arr[nr][nc] == 'S') {
					return false;
				}
				nr += dr[d], nc += dc[d];
			}
		}
	}
	return true;
}



void dfs(int depth) {
	if (answer)return;
	if (depth == 3) {
		if (isValid())answer = true;
		return;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i][j] != 'X')continue;
			arr[i][j] = 'O';
			dfs(depth + 1);
			arr[i][j] = 'X';
		}
	}
	

}



int main() {
	//매번 최대한 많은  선생 <> 학생 이 가려지도록 
	

	//선생 - 학생 선분을 모두 구하고
	//

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'S')stu.push_back({ i,j });
			else if (arr[i][j] == 'T')teach.push_back({ i,j });
		}
	}
	dfs(0);
	if (answer) cout << "YES";
	else cout << "NO";

}

 

 

Trouble Shooting

 

해당 문제에서는 배열이 6*6으로 매우 작기에 위와 같이 완전 탐색으로 푸는 것이 아무런 문제 없지만, 연습 겸 해당 문제를 '선분' 정보를 활용해서 해결하려고 했다.

 

각 선생님은 자신의 위치에서 상,하,좌,우로 끝까지 확인하여 학생을 감지할 수 있다. 

'선분' 은 2개의 정점으로 구성되어지기에, 각 방향을 선분 정보로 저장하려 시도했다.

 

[예시]
특정 선생님의 위치가 {a,b}라고 가정하고, N이 가장 바깥쪽의 idx라고 가정한다면
{a,b}  <> {a,0}  (왼쪽 선분)
{a,b}  <> {a,N} (오른쪽 선분)
{a,b}  <> {0,b} (윗쪽 선분)
{a,b}  <> {N,b} (윗쪽 선분

 

위와 같이 주어진 선분 정보를 모두 저장하는 것이 처음이었다.

 

이때 로직을 발전시켜 각각 학생 - 선생 으로 이어지는 선분 정보를 모두 저장하고, 만약 교차되는 선분이 있다면 선분을 저장한 벡터에서 저장 시키는 것으로 교차점에 무조건 장애물을 두며 나아간다는 로직을 구성했다. 

하지만, 교차점이 제거되는 순서에 따라 제거할 수 있는 선분의 개수가 달라지는 문제가 발견되어 이 로직은 실패였다.

하지만 이는 로직의 문제이고, 여전히 '선분 교차'를 통해 각 선생이 학생을 볼 수 있나 없나를

O(N) 이 아닌 O(1)으로 찾을 수 있는 것은 유효하기에, 아래 코드를 '참고만' 해두자.

 

 

오답 코드( 선분 교차)

#include<iostream>
#include<vector>
using namespace std;
char arr[6][6];
int obj_num = 3;
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
int N;


struct Line {
	pair<int, int> low;  //a ->b 가 idx 증가하는 방향 (stu,teach 무관 )
	pair<int, int> high;
	bool vertical; //수직 선분?
};
vector<Line> lines;

bool removeCross(Line newLine) {
	//cout <<lines.size()<< ": =========================================" << endl;
	for (int i = 0; i < lines.size(); i++) {
		Line oldLine = lines[i];
		//cout << "old: " << oldLine.low.first << ", " << oldLine.low.second << " => " << oldLine.high.first << ", " << oldLine.high.second << endl;
		//cout << "new: " << newLine.low.first << ", " << newLine.low.second << " => " << newLine.high.first << ", " << newLine.high.second << endl;
		//cout << endl;
		if (oldLine.vertical == newLine.vertical) return false;
		Line ver, hor;
		if (oldLine.vertical) {
			ver = oldLine;
			hor = newLine;
		}
		else {
			ver = newLine;
			hor = oldLine;
		}
		int hor_r = hor.low.first, ver_c = ver.low.second;//어차피 각각 low, high 둘다 같은 값
		if (ver.low.first < hor_r && hor_r < ver.high.first) {
			if (hor.low.second < ver_c && ver_c < hor.high.second) {
				lines.erase(lines.begin() + i);
				//cout << "위에가 교차!==================" << endl;
				return true; //만약 교차하는것이 존재한다면, 해당 선분 제거
			}
		}
	}
	return false;
}


void right(int r, int c) {
	for (int i = c + 1; i < N; i++) {
		if (arr[r][i] == 'S') {
			//cout << "find! :" << r << ", " << c << " : right!" << endl;
			Line tmp = { { r,c }, { r,i }, false };
			removeCross(tmp);
			lines.push_back({ {r,c},{r,i},false });
			break;
		}
	}
}

void left(int r, int c) {
	for (int i = c -1; i>=0; i--) {
		if (arr[r][i] == 'S') {
			//cout << "find! :" << r << ", " << c << " : left!" << endl;
			Line tmp = { {r,i},{r,c},false };
			removeCross(tmp);
			lines.push_back(tmp);
			break;
		}
	}
}
void down(int r, int c) {
	for (int i = r + 1; i < N; i++) {
		if (arr[i][c] == 'S') {
			//cout << "find! :" << r << ", " << c << " : down!" << endl;
			Line tmp = { {r,c},{i,c},true };
			removeCross(tmp);
			lines.push_back(tmp);
			break;
		}
	}
}
void up(int r, int c) {
	for (int i = r - 1; i >= 0; i--) {
		if (arr[i][c] == 'S') {
			//cout << "find! :" << r << ", " << c << " : up!" << endl;
			Line tmp = { {i,c},{r,c},true };
			removeCross(tmp);
			lines.push_back(tmp);
			break;
		}
	}
}

void addLine(int r,int c) {
	left(r, c);
	right(r, c);
	up(r, c);
	down(r, c);
}


int main() {
	//매번 최대한 많은  선생 <> 학생 이 가려지도록
	vector<pair<int, int>> stu;
	vector<pair<int, int>> teach;

	//선생 - 학생 선분을 모두 구하고
	//

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'S')stu.push_back({ i,j });
			else if (arr[i][j] == 'T')teach.push_back({ i,j });
		}
	}

	for (int i = 0; i < teach.size(); i++) {
		int t_r = teach[i].first, t_c = teach[i].second;
		addLine(t_r, t_c);
	}
	if (lines.size() <= 3)cout << "YES"<<endl;
	else cout << "NO"<<endl;


	cout << lines.size();
}

 

 

 

만약 N이 매우 거대해 '선분 교차' 로직이 필요한 문제를 풀어보고 싶다면 아래 문제를 풀어보자!

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

10875번: 뱀