2021 카카오 채용연계형 인턴십 > 거리두기 확인하기

1. 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

 

2. 풀이

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

class Pos {
public:
	int r, c;
	Pos(int r, int c) {
		this->r = r;
		this->c = c;
	}
};

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

bool check2(Pos start, const vector<string>& board) {
	//start 위치 주변으로 접촉자 없으면 true 있으면 false
	bool visited[5][5];
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			visited[i][j] = false;
		}
	}
	queue<Pos> q;
	q.push(start);
	visited[start.r][start.c] = true;
	for (int i = 0; i < 2; i++) {	//2번 반복 => 거리가 2인것 까지만 탐색
		int len = q.size();
		for (int j = 0; j < len; j++) {
			Pos currentP = q.front(); q.pop();
			for (int k = 0; k < 4; k++) {
				Pos nextP = { currentP.r + dx[k], currentP.c + dy[k] };
				if (nextP.r >= 0 && nextP.r < 5 && nextP.c >= 0 && nextP.c < 5 && !visited[nextP.r][nextP.c]) {
					if (board[nextP.r][nextP.c] == 'P')
						return false;

					if (board[nextP.r][nextP.c] == 'O') {
						q.push(nextP);
						visited[nextP.r][nextP.c] = true;
					}
				}
			}
		}
	}
	
	//발견 안되었다면
	return true;
}

int check(vector<string> board) {
	//잘 지키고 있으면 1 아니면 0리턴
	for (int r = 0; r < board.size(); r++) {
		for (int c = 0; c < board[0].size(); c++) {
			if (board[r][c] == 'P' && !check2({ r,c }, board)) {
				return 0;
			}
		}
	}
	return 1;
}

vector<int> solution(vector<vector<string>> places) {
	vector<int> answer;

	for (int i = 0; i < places.size(); i++)
		answer.push_back(check(places[i]));

	return answer;
}

보드 크기가 5x5이기 때문에 전수조사가 가능하다.

또한, 확인해야 하는 것은 거리가 2 이하인 지점에 또 다른 사람이 있는지 이기 때문에 BFS 탐색을 할 때 전역 탐색하지 않고 2번만 루프를 돌면 된다.