[Softeer] 좌석 관리

문제링크 : https://softeer.ai/practice/info.do?idx=1&eid=625&sw_prbl_sbms_sn=99436

현재 앉아있는 모든 사람 vs 현재 비어있는 자리 찾기!!

💻 문제 풀이 : C++

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

#define MAX 25
using namespace std;

struct Seat {
	int row, col;
	int state;
};

int N, M, Q;
int dr[4] = { 0, -1, 1, 0 };
int dc[4] = { -1, 0, 0, 1 };
int MAP[MAX][MAX];
struct Seat seat[10001];
vector<int> v_id;

int getDist(int r, int c)
{
	int minDist = 213567890;
	for (int i = 0; i < v_id.size(); i++)
	{
		int nowDist = (r - seat[v_id[i]].row) * (r - seat[v_id[i]].row) + (c - seat[v_id[i]].col) * (c - seat[v_id[i]].col);
		if (minDist > nowDist)
			minDist = nowDist;
	}
	return minDist;
}

int isSafe(int row, int col)
{
	if (row <= 0 || col <= 0 || row > N || col > M) return 0;
	for (int i = 0; i < 4; i++)
	{
		int nr = row + dr[i];
		int nc = col + dc[i];
		if (MAP[nr][nc] == 1) return 0;
	}
	return 1;
}

// 지금 앉을 자리를 정하는 함수
void getSeat(int *nowRow, int *nowCol, int nowSeat)
{
	if (nowSeat == 0)
	{
		*nowRow = 1;
		*nowCol = 1;
		return;
	}
	int maxDist = -1;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (MAP[i][j] == 1) continue;
			if (!isSafe(i, j)) continue;
			int nowDist = getDist(i, j);
			if (maxDist == nowDist) {
				if (*nowRow > i) {
					*nowRow = i;
					*nowCol = j;
				}
				else if (*nowRow == i && *nowCol > j) {
					*nowRow = i;
					*nowCol = j;
				}
			}
			else if (maxDist < nowDist)
			{
				maxDist = nowDist;
				*nowRow = i;
				*nowCol = j;
			}
		}
	}
}

int main()
{
	cin >> N >> M >> Q;
	for (int i = 0; i < Q; i++)
	{
		string cmd;
		int id;
		int row = 0;
		int col = 0;
		cin >> cmd >> id;
		if (cmd == "In")
		{
			if (seat[id].state == 0) {
				getSeat(&row, &col, v_id.size());
				if (row == 0 && col == 0) {
					cout << "There are no more seats.\n";
					continue;
				}
				seat[id].state = 1;
				seat[id].row = row;
				seat[id].col = col;
				MAP[row][col] = 1;
				v_id.push_back(id);
				cout << id << " gets the seat (" << row << ", " << col << ").\n";
			}
			else if (seat[id].state == 1) {
				cout << id << " already seated.\n";
			}
			else if (seat[id].state == 2){
				cout << id << " already ate lunch.\n";
			}

		}
		else if (cmd == "Out")
		{
			if (seat[id].state == 0) {
				cout << id << " didn't eat lunch.\n";
			}
			else if (seat[id].state == 1) {
				seat[id].state = 2;
				for (int v = 0; v < v_id.size(); v++)
					if (v_id[v] == id)
						v_id.erase(v_id.begin() + v);
				MAP[seat[id].row][seat[id].col] = 0;
				cout << id << " leaves from the seat (" << seat[id].row << ", " << seat[id].col << ").\n";
			}
			else if (seat[id].state == 2) {
				cout << id << " already left seat.\n";
			}
		}
	}
	return 0;
}

📌 memo 😊

// vector에서 특정 index 제거하기
v.erase(v.begin() + idx

문제 해결 과정

1. DFS로 최대 안전도인 자리를 찾자!
   --> 재귀 종료조건을 정하기가 어려웠음 😂
   (아마도 visited로 인해 저절로 종료되었을듯...?)

2. BFS로 찾아보자!
   --> 한칸씩 탐색하기 때문에 "거리두기" 조건 성립 여부를 확인하기 어려움
   (하지만 BFS도 마찬가지로 visited로 저절로 종료되었을수도 있음)

3. 그냥 for문으로 모든 MAP을 탐색하자!
   --> 문제 해결의 핵심은 시간복잡도 파악임
   --> 최악의 경우 20 x 20 x 20 x 10^4임
   --> 하지만 처음 문제를 풀때는 20 x 20 x 3 x 10^4 x 10^4으로 잘못 생각... 😒

---

문제를 해결할 때 가장 중요한 것은 해결의 "방향"임.
하지만 방향이 "올바른"지 "아닌"지는 모름
따라서 문제 해결의 순서는
1. 입출력과 같이 ✨간단한 부분✨ 먼저 구현
2. 해결해야 하는 부분만 따로 ✨추상화 구현✨
3. 추상화 함수의 ✨핵심 조건✨ 을 정리
--> 지금 문제 같은 경우, MAP이 작기 때문에 "그냥" 전체탐색을 하면 됨
4. 🔍탐색🔍과 같이, 반복문으로 하기 싫더라도 일단 구현하자!
(단순히 구현해 놓을 수 있는 부분을 멋있게 풀려고 하면 시간이 너무 소요됨...!)