✅ What I did today

---

• 백준

⚔️ 백준

---

16236 아기 상어

#include"16236.h"
using namespace std;
typedef pair<int, int> pii;

// 실수 1. found에 넣는거 자체는 먹는게 아니라 
// 먹을 수 있는 후보인데 mat 값을 초기화시켜버림
// 실수 2. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.
// 국어 지문 해석을 잘못함. '당연히' 먹으면 레벨이 오를거라 생각해버린 실수.
// 문제가 일부러 헷갈리게 서술된 면도 있긴 함.

void B16236::Solution()
{
	vector<int> dx = { 1,-1,0,0 };
	vector<int> dy = { 0,0,1,-1 };

	int N;
	cin >> N;
	vector<vector<int>> mat(N,vector<int>(N));
	pii shark;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> mat[i][j];
			if (mat[i][j] == 9) { 
				shark = { i,j };
				mat[i][j] = 0;
			};
		}
	}

	// 한 번 움직일때마다 bfs 하는 시뮬레이션
	// 먹을 수 있는 놈 찾을 때까지 bfs
	// 거리가 같으면 i가 작은 거, 그것도 같으면 j가 작은거 우선
	// 크기가 같으면 먹진 못하고 통과는 가능
	int time = 0;
	int level = 2;
	int eaten = 0;
	while (1)
	{
		queue<pii> q;
		q.push(shark);
		int dist = 0;
		vector<pii> found;
		vector<vector<bool>> visited(N, vector<bool>(N, false));
		while (!q.empty())
		{
			dist++;
			int qlen = q.size();
			for (int i = 0; i < qlen; ++i) {
				int x = q.front().first;
				int y = q.front().second;
				q.pop();

				for (int k = 0; k < 4; ++k) {
					int newx = x + dx[k];
					int newy = y + dy[k];
					if (0 <= newx && newx < N && 0 <= newy && newy < N
						&& !visited[newx][newy]) {
						if (mat[newx][newy] == 0) {
							q.push({ newx,newy });
						}
						else if (mat[newx][newy] < level) {
							found.push_back({ newx,newy });
						}
						else if (mat[newx][newy] == level) {
							q.push({ newx,newy });
						}
						visited[newx][newy] = true;
					}
				}
			}
			if (!found.empty()) break;
		}

		if (found.empty()) break;
		int minfx = N;
		int minfy = N;
		for (pii f : found) {
			int fx = f.first, fy = f.second;
			if (fx < minfx || (fx == minfx && fy < minfy)){ 
				minfx = fx; minfy = fy; 
			}
		}
		eaten += 1;
		if (eaten == level) {
			eaten = 0;
			level++;
		}
		time += dist;
		mat[minfx][minfy] = 0;
		shark = { minfx, minfy };
	}
	cout << time;
}

1948 임계경로

틀린 풀이 : dfs

#include"1948.h"
using namespace std;
typedef pair<int, int> pii;

vector<map<int,int>> graph;
vector<int> parent;
vector<vector<bool>> max_course_road;
int n, m;
int start_city = 0;
int arrive_city = 0;
int max_time = 0;
int total_time = 0;

void dfs(int sc)
{
	if (sc == arrive_city) {
		if (max_time > total_time) return;
		if (max_time < total_time) {
			max_time = total_time;
			max_course_road = vector<vector<bool>>(n+1,vector<bool>(n+1,false));
		}
		int city = sc;
		while (city != start_city) {
			max_course_road[parent[city]][city] = true;
			city = parent[city];
		}
		return;
	}

	for (pii edge : graph[sc]) {
		int nc = edge.first;
		int time = edge.second;
		parent[nc] = sc;
		total_time += time;
		dfs(nc);
		total_time -= time;
	}
}

void B1948::Solution()
{
	// 인덱스랑 실제 번호랑 헷갈리는거 주의
	// dfs 하고 최장 길이 갱신되면 경로 역추적해서 노드 세기

	cin >> n; // 도시의 개수
	cin >> m; // 도로의 개수
	graph = vector<map<int,int>>(n+1);
	parent = vector<int>(n + 1);
	max_course_road = vector<vector<bool>>(n + 1, vector<bool>(n + 1, false));

	int start, arrive, time;
	for (int i = 0; i < m; ++i) {
		cin >> start >> arrive >> time;
		graph[start][arrive] = time;
	}

	cin >> start_city >> arrive_city;

	dfs(start_city);
	cout << max_time << endl;
	int max_course_count = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (max_course_road[i][j]) max_course_count++;
		}
	}
	cout << max_course_count << endl;
}

예전에 풀때도 dfs인줄만 알았었는데, 또 속고 시간을 낭비해버렸다.
예전 풀이 과정 확인하여 위상 정렬인거 확인

맞는 풀이 : 위상 정렬

#include"1948.h"
using namespace std;
typedef pair<int, int> pii;
#define INF 0x3f3f3f3f

void B1948::Solution()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	// 인덱스랑 실제 번호랑 헷갈리는거 주의
	// dfs 하고 최장 길이 갱신되면 경로 역추적해서 노드 세기

	int n, m;
	cin >> n; // 도시의 개수
	cin >> m; // 도로의 개수
	vector<vector<pii>> graph(n+1);
	vector<int> indegree(n + 1);
	vector<int> max_time(n + 1, 0);
	vector<vector<int>> pre_node(n + 1);
	vector<bool> visited(n + 1, false);

	int start, arrive, time;
	for (int i = 0; i < m; ++i) {
		cin >> start >> arrive >> time;
		graph[start].push_back({arrive,time});
		indegree[arrive]++;
	}

	int start_city, arrive_city;
	cin >> start_city >> arrive_city;

	queue<int> q;
	q.push(start_city);
	while (!q.empty()) {
		start = q.front();
		q.pop();
		for (pii edge : graph[start]) {
			arrive = edge.first;
			time = edge.second;
			if (max_time[arrive] == time + max_time[start]) {
				pre_node[arrive].push_back(start);
			}
			else if (max_time[arrive] < time + max_time[start]) {
				max_time[arrive] = time + max_time[start];
				pre_node[arrive] = { start };
			}
			indegree[arrive]--;
			if (indegree[arrive] == 0) {
				q.push(arrive);
			}
		}
	}
	int max_time_road = 0;
	q.push(arrive_city);
	while (!q.empty()) {
		int node_e = q.front(); q.pop();
		for (int node_s : pre_node[node_e]) {
			max_time_road++;
			if (visited[node_s]) continue;
			q.push(node_s);
			visited[node_s] = true;
		}
	}
	cout << max_time[arrive_city] << endl;
	cout << max_time_road << endl;
}

위상 정렬은 역재귀로 풀면 더 간단해지긴 하는데 예전에 역재귀로 풀었어서 이번엔 정석 위상 정렬로