[코드트리] 코드트리 빵

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=3&pageSize=20

💻 문제 풀이 : C++

#### 풀이 실패...! (98% 🤣)

// Warning!
// 1. BaseCamp와 편의점은 갈 수 없다?! => "도착한". "출발한"??
// 2. 중간에 비어있는 벡터 어떻게 처리? => 과제
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

#define MAP_SIZE 20

using namespace std;

struct Coord{
	int row;
	int col;
};

int n, m;
int MAP[MAP_SIZE][MAP_SIZE];
int visited[MAP_SIZE][MAP_SIZE];

queue<Coord> store;
vector<Coord> basecamp;
vector<int> moving;
vector<Coord> matched;
queue<int> duration;

// 상, 좌, 우, 하 의 반대 아닐까??
// 하, 우, 좌, 상
// 상, 좌, 우, 하 가 맞는듯??
int dr[] = {-1, 0, 0, 1};
int dc[] = {0, -1, 1, 0};

void CLEAR()
{
	n = 0;
	m = 0;
	memset(MAP, 0, sizeof(MAP));
	memset(visited, 0, sizeof(visited));
	while (!store.empty())
		store.pop();
	basecamp.clear();
	matched.clear();
	while (!duration.empty())
		duration.pop();
}

void INPUT()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1 ; j <= n; j++)
		{
			cin >> MAP[i][j];
			if (MAP[i][j] == 1)
				basecamp.push_back({ i,j });
		}
	}
	for (int i = 0; i < m; i++)
	{
		int row, col;
		cin >> row >> col;
		store.push({ row, col });
		MAP[row][col] = 2;
	}
}

void bfs(Coord start)
{
	queue<Coord> nowQ;
	nowQ.push(start);
	while (!nowQ.empty())
	{
		Coord now = nowQ.front();
		nowQ.pop();
		for (int i = 0; i < 4; i++)
		{
			int next_row = now.row + dr[i];
			int next_col = now.col + dc[i];
			if (next_row <= 0 || next_col <= 0 || next_row > n || next_col > n) continue;
			if (MAP[next_row][next_col] == 2) continue;
			if (MAP[next_row][next_col] == 1) {
				matched.push_back({ next_row, next_col });
				MAP[next_row][next_col] = 3;
				duration.push(visited[now.row][now.col]);
				return;
			}
			if (visited[next_row][next_col] != 0) continue;
			visited[next_row][next_col] = visited[now.row][now.col] + 1;
			nowQ.push({ next_row, next_col });
		}
	}
}

void SOLVE()
{
	// 편의점 큐 순회하면서 최단거리 베이스캠프 찾기
	while (!store.empty())
	{
		memset(visited, 0, sizeof(visited));
		visited[store.front().row][store.front().col] = 1;
		bfs(store.front());
		store.pop();
	}
	int time = 0;
	while (time < 1000)
	{
		time++;
		int size = moving.size();
		for (int i = 0; i < size; i++)
			moving[i]--;
		sort(moving.begin(), moving.end(), greater<int>());
		while (!moving.empty() && moving.back() == 0)
		{
			if(moving.back() <= 0) moving.pop_back();
		}
		if (!duration.empty())
		{
			moving.push_back(duration.front());
			duration.pop();
		}
		if (moving.empty() && time > 1) break;
	}
	cout << time << "\n";
}

int main()
{
	CLEAR();
	INPUT();
	SOLVE();

	int debug = 0;

	return 0;
}

Feedback

1. 근본적으로 구현은 문제 요구에 따라서
   => 시키는 대로만 해야함...!
   => 이 풀이는 시키는 대로 하지 않기 위한(편하게 하기 위해서) 구현법임
   => 개발자는 요구사항에 맞춰서 개발해야한다...

2. vector 비우기 어떻게...?
   => 배열 조작(0으로 만들기 등등...)한 후에
   => O(N^2) 순회하면서 sort?

👿 문제대로 한다면 이동경로를 어떻게 설정할지...?!

---

📌 memo 😊