굳건하게

문제 : https://www.acmicpc.net/problem/2623

위상정렬

● inDegree가 0인 지점부터 시작해서 위상 정렬을 진행한다. 이때, 탐색하는 순서대로 노드들을 vector<int> ans 에 저장하고, 탐색한 노드들을 check 한다. 탐색이 끝나면 모든 노드들을 check 했다면 가능한 순서쌍이 존재하는 것이므로 ans를 차례대로 출력해주고, 모든 노드들을 check 하지 못했다면 불가능한 경우이므로 0을 출력한다.

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int N, M, inDegree[1001];
vector<int> graph[1001] = {};
vector<int> ans;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	// Input 처리
	cin >> N >> M;
	for (int i = 0, k; i < M; i++) {
		int list[1000];
		cin >> k;
		for (int j = 0; j < k; j++)
			cin >> list[j];
		for (int j = 0; j < k - 1; j++){
			graph[list[j]].push_back(list[j + 1]);
			inDegree[list[j + 1]]++;
		}
	}
	// 위상정렬
	stack<int> s;
	bool check[1001] = {};
	for (int i = 1; i <= N; i++)
		if (inDegree[i] == 0)
			s.push(i);
	while (!s.empty()) {
		int cur = s.top(); s.pop();
		ans.push_back(cur);
		check[cur] = true;
		for (int i = 0; i < graph[cur].size(); i++) {
			inDegree[graph[cur][i]]--;
			if (inDegree[graph[cur][i]] == 0)
				s.push(graph[cur][i]);
		}
	}
	// 다 체크되었는지!
	bool flag = false;
	for (int i = 1; i <= N; i++) {
		if (check[i] == 0){
			flag = 1;
			break;
		}
	}
	if (!flag) {
		for (int j = 0; j < ans.size(); j++)
			cout << ans[j] << '\n';
	}
	else
		cout << 0;

	return 0;
}

문제 : https://www.acmicpc.net/problem/2493

스택 Stack

● 자료구조 스택을 이용하면 입력된 값을 역으로 순회하며 문제를 해결할 수 있다.

● 현재 스택이 비어있다면, 스택에 Push

● 스택에 값이 있다면, 스택의 top과 현재 값을 비교해 현재 값보다 스택의 top이 작다면 top에 해당하는 원소는 현재 값에 신호를 보내게 되므로 답을 갱신하고 스택을 pop하고 다시 이 과정을 반복한다.

( 답 갱신하는 과정을 위해 스택에 { 값, index } 를 같이 push 해준다. )

#include<iostream>
#include<stack>

using namespace std;

int N, list[500001], ans[500001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> list[i];

	stack<pair<int, int>> s;
	for (int i = N; i > 0; i--) {
		if (s.empty()) {
			s.push({ list[i], i });
		}
		else {
			while (s.top().first < list[i]) {
				ans[s.top().second] = i;
				s.pop();
				if (s.empty())
					break;
			}
			s.push({ list[i], i });
		}
	}
	for (int i = 1; i <= N; i++)
		cout << ans[i] << ' ';
	return 0;
}

문제 : https://www.acmicpc.net/problem/14442

BFS 탐색

● 단순 BFS 탐색을 수행해서 (0, 0) 에서 ( N - 1, M - 1 ) 까지 이동이 가능한지 탐색하면 되는데 최대 K 개 만큼의 벽을 부셔도 되므로, visited 배열을 2차원이 아닌 3차원으로 visited[N][M][K] 로 만들어줘야합니다.

visited[X][Y][T] := (X, Y) 지점에 벽을 T개 부수고 도착한 적이 있는지 없는지.

● 큐에는 현재 내 위치 좌표와 몇 번 벽을 부수고 이동했는지, 이동 횟수 총 4가지 정보를 담습니다.

queue<pair<pair<int, int>, pair<int, int>> q;

● 내가 이동해야하는 곳이 '1' 벽이라면 현재 벽을 부순 횟수 + 1 이 K 이하인지 체크하고, visited[curX][curY][현재벽을부순횟수 + 1] 을 방문하지 않았다면 큐에 담아줍니다.

● 내가 이동해야하는 곳이 '0' 이라면 visited[curX][curY][현재벽을부순횟수] 를 방문하지 않았다면 큐에 담아줍니다.

#include<iostream>
#include<queue>

using namespace std;

int N, M, K, dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
bool visited[1000][1000][10];
char map[1000][1001];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	queue<pair<pair<int, int>, pair<int, int>>> q;
	visited[0][0][0] = 1;
	q.push({ {0, 0}, { 0, 0 } });

	bool flag = false;
	while (!q.empty()) {
		pair<pair<int, int>, pair<int, int>> temp = q.front();
		q.pop();
		int curX = temp.first.first, curY = temp.first.second;
		int curW = temp.second.first, curL = temp.second.second;
		
		if (curX == N - 1 && curY == M - 1) {
			cout << curL + 1 << '\n';
			flag = true;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nX = curX + dx[i], nY = curY + dy[i];
			if (!(0 <= nX && nX < N && 0 <= nY && nY < M))
				continue;
			if (map[nX][nY] == '0' && visited[nX][nY][curW] == 0) {
				visited[nX][nY][curW] = 1;
				q.push({ {nX, nY}, {curW, curL + 1} });
			}
			if (map[nX][nY] == '1' && visited[nX][nY][curW + 1] == 0 && curW + 1 <= K){
				visited[nX][nY][curW + 1] = 1;
				q.push({ {nX, nY}, {curW + 1, curL + 1} });
			}
		}
	}
	if (!flag)
		cout << -1 << '\n';
	return 0;
}

문제 : https://www.acmicpc.net/problem/1005

위상정렬

위상정렬 문제로 endNode 까지 도착하는데 가장 긴 경로를 구하면 된다.

자세한 풀이는 BOJ 1516 게임 개발 풀이를 참고해주시면 감사합니다. 

(https://travelbeeee.tistory.com/375)

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while(t--){
		int N, K, endGame, time[1001] = {}, inDegree[1001] = {}, ans[1001] = {};
		vector<int> graph[1001];
		stack<int> s;

		cin >> N >> K;
		for (int i = 1; i <= N; i++)
			cin >> time[i];
		for (int i = 0, x, y; i < K; i++) {
			cin >> x >> y;
			graph[x].push_back(y);
			inDegree[y]++;
		}
		cin >> endGame;

		for (int i = 1; i <= N; i++)
			if (inDegree[i] == 0){
				s.push(i);
				ans[i] = time[i];
			}

		while (!s.empty()) {
			int cur = s.top();
			s.pop();
			if (cur == endGame) {
				cout << ans[cur] << '\n';
				break;
			}
			for (int i = 0; i < graph[cur].size(); i++) {
				inDegree[graph[cur][i]]--;
				ans[graph[cur][i]] = max(ans[graph[cur][i]], ans[cur] + time[graph[cur][i]]);
				if (inDegree[graph[cur][i]] == 0) {
					s.push(graph[cur][i]);
				}
			}
		}
	}
	return 0;
}