[프로그래머스] 거리두기 확인하기 (C++) (2021 카카오 채용연계형 인턴십)

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

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

2021 카카오 채용연계형 인턴십 코테에서 직접 풀었던 문제이다. 

그때도 이 문제는 해결했지만... 살짝 하드코딩을 했던 기억이 있다. (이 다음문제인 3번에서 .5솔로 총 2.5솔로 뜨거운 불합격을 했던 기억이 있다)

 

그때보다 훨씬 깔끔한 코드로 다시 풀어보았다.

이 문제의 핵심은 각 파티션인 경우를 제외하고 맨해튼 거리가 2이하인 경우만 탐색하는 것이다. 이 조건 아래 탐색 도중 응시자를 만나게 된다면 거리두기를 어기는 것이다.

 

DFS로 구현하였다.

전체코드는 아래와 같다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

char map[5][5];
int visit[5][5];
vector<pair<int, int>> person;
int dx[4] = { 0,0,1,-1};
int dy[4] = { 1,-1,0,0};
bool flag = true;

void dfs(int x, int y, int depth) {
	if (depth > 2) return; //맨해튼 거리가 3이상이면 탐색 x

	if (depth > 0 && map[x][y] == 'P') { //맨해튼 거리가 2이하일때 사람 만난경우
		flag = false;
		return;
	}
	visit[x][y] = 1;
	for (int i = 0; i < 4; i++){
		int cx = x + dx[i];
		int cy = y + dy[i];
		if (cx >= 0 && cx < 5 && cy >= 0 && cy < 5 && !visit[cx][cy] && map[cx][cy] != 'X') {//중요 : 파티션이 아닌경우
			dfs(cx, cy, depth + 1);
		}
	}
}

int solve() {
	flag = true;
	for (int i = 0; i < person.size(); i++){		
		dfs(person[i].first,person[i].second , 0);
		if (!flag) return 0;
	}
	return 1;
}

vector<int> solution(vector<vector<string>> places) {
	vector<int> answer;
	for (int i = 0; i < places.size(); i++){
		person.clear();
		memset(visit, 0, sizeof(visit));
		for (int j = 0; j < 5; j++){
			for (int k = 0; k < 5; k++) {
				map[j][k]= places[i][j][k];
				if (map[j][k] == 'P') person.push_back({ j,k });
			}
		}
		int result = solve();
		answer.push_back(result);
	}

    return answer;
}