SWEA 2383번 [모의 SW 역량테스트] 점심 식사시간 C++ DFS, 시뮬레이션, 우선순위 큐

리뷰

DFS를 통한 완전탐색과, PQ를 통한 값 비교, 시뮬레이션 까지 필요한 까다로운 문제

 

 

SW Expert Academy

 

문제 풀이

각 테스트 케이스 마다 init과 input, solution으로 나누어 진행하였다.

init에서는 각 테스트 케이스마다 초기값을 세팅해 준다.

input에서는 맵 정보와 사람, 계단 정보를 받아와 초기화 해준다.

solution에서는 DFS를 실행하고, DFS 내부적으로 재귀를 거치며 기저조건에 달성하면 시뮬레이션을 돌려준다.

모든 재귀가 종료되고 나면 ans에 저장 되어 있는 값을 각 테스트 케이스마다 출력해주면 된다.

 

참고 사항

1. init()

1. 맵 정보를 모두 0으로 초기화 해준다.
2. ans의 값을 큰 값으로 설정해 준다.
3. 사람, 계단, 경로에 해당하는 vector를 모두 clear 해준다.

2. input()

1. n값을 받아오고 n * n 크기의 맵을 초기화 해준다.
2. 입력 값이 1일 경우 각 사람의 좌표를 people 벡터에 추가해 준다.
3. 입력 값이 2이상일 경우 계단의 좌표를 stairs 벡터에 추가해 준다.

3. solution()

1. dfs를 level 0부터 돌려준다.

4. dfs(int now)

1. 매개변수 now는 사람 수에 해당하며 people.size()에 달하게 되면 simulation 함수를 돌리고 리턴한다.
2. 계단은 총 두개가 존재하니 사람들이 각 계단을 탄 부분을 완전 탐색으로 돌려준다.
3. for문은 각 계단을 탔을때로 가정하고, path 벡터에 해당 사람이 사용한 계단을 기록해 준 뒤 level을 증가시켜 재귀를 돌려준다. 이후 재귀를 빠져나올때 path에 설정해 주었던 경로를 원상복구 해준다.

5. simulation()

1. 계단까지의 이동 및 계단을 타고 나오는 부분을 시뮬레이션을 해준다.
2. pq는 계단의 숫자에 맞게 2개를 준비해 준다.
3. for문을 통해 각 사람의 정보를 받아오고, 해당 사람의 인덱스와 사용한 계단을 통해 거리를 계산해 준다.
4. 만약 현재 계단을 사용한 사람이 3명 미만인 경우 큐에 계단까지의 이동시간 + 1 + 계단 이용시간을 push
5. 만약 3명 이상인 경우 가장 첫번째 사람을 pop해주고, 해당 사람의 계단 이용시간과 현재 사람의 계단 이동시간을 비교하여 더 큰 값과 계단 이용시간을 더해 push 해준다.
6. 큐를 모두 탐색하며 맨 마지막 사람이 계단을 이용하는 것을 체크하고 더 큰 값을 리턴해 준다.

※ calcdist(const Coord& a, const Coord& b)

사람과 계단 사이의 거리를 구하는 함수

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

struct Coord {
	int row, col;
};

int calcdist(const Coord& a, const Coord& b) {
	return abs(a.row - b.row) + abs(a.col - b.col);
}

struct Element {
	Coord person;
	Coord stair;
	bool operator<(const Element& other) const {
		return calcdist(person, stair) > calcdist(other.person, other.stair);
	}
};

vector<Coord> people;
vector<Coord> stairs;
vector<int> path;

int tc, n, ans;
int lst[10][10];

void init() {
	memset(lst, 0, sizeof(lst));
	ans = 1e9;
	people.clear();
	stairs.clear();
	path.clear();
}

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lst[i][j];
			if (lst[i][j] == 1) people.push_back({ i, j });
			else if (lst[i][j] >= 2) stairs.push_back({ i, j });
		}
	}
}

int simulation() {
	priority_queue<Element> pq[2];
	for (int i = 0; i < path.size(); i++) {
		int person = i;
		int stair = path[i];
		pq[stair].push({ people[i], stairs[stair]});
	}
	int a = 0;
	for (int i = 0; i < 2; i++) {
		queue<int> q;
		while (!pq[i].empty()) {
			Element element = pq[i].top(); pq[i].pop();
			int arriveT = calcdist(element.person, element.stair) + 1;
			int stairT = lst[element.stair.row][element.stair.col];
			if (q.size() < 3) q.push(arriveT + stairT);
			else {
				int prev = q.front(); q.pop();
				if (prev > arriveT) q.push(prev + stairT);
				else q.push(arriveT + stairT);
			}
		}
		while (!q.empty()) {
			a = max(a, q.front());
			q.pop();
		}
	}
	return a;
}

void dfs(int now) {
	if (now >= people.size()) {
		ans = min(ans, simulation());
		return;
	}

	for (int i = 0; i < 2; i++) {
		path.push_back(i);
		dfs(now + 1);
		path.pop_back();
	}
}

void solution() {
	dfs(0);
}

int main() {
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		init();
		input();
		solution();
		cout << "#" << t << " " << ans << "\n";
	}
}