백준 31854 - 부등호 퍼즐(C++)

문제 링크입니다. https://www.acmicpc.net/problem/31854

 

어떤 알고리즘을 사용해야 되는지 파악하는 하는게 중요한 문제입니다.

 

각 좌표들의 부등호가 주어질 때, 이를 통해서 올바른 퍼즐을 구하는 문제입니다.

 

(X, Y)  좌표와 (X, Y + 1), (X + 1, Y)의 관계가 주어지는데, 이때 어느 쪽이 큰지, 작은지를 알 수 있기에 이는 방향성이 있는 그래프로 생각할 수 있습니다.

 

또한, 가장 작은 곳부터 순서대로 채워나가면 되기에, 자기보다 큰 좌표가 있다면 해당 좌표의 값을 하나씩 증가시키면서 나중에 채워나가면 된다는 생각을 할 수 있습니다.

 

위의 2개를 합치면 위상 정렬이 되기에 위상 정렬의 조건에 맞춰서 구현해주시면 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

int N;
vector<int> connect[1000 * 1000 + 1];
int Step[1000 * 1000 + 1];
int map[1001][1001];
queue<int> q;

void fill_puzzle(int loc, int num) {
	int x, y;
	if (loc % N == 0) {
		x = loc / N;
		y = N;
	}
	else {
		x = loc / N + 1;
		y = loc % N;
	}
	// cout << x << " " << y << "\n";
	map[x][y] = num;
}

void topological_sort() {
	int num = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		fill_puzzle(x, num++);
		for (int i = 0; i < connect[x].size(); i++) {
			int xx = connect[x][i];
			Step[xx]--;
			if (Step[xx] == 0) q.push(xx);
		}
	}
}

void solve() {
	for (int i = 1; i <= N * N; i++) {
		if (Step[i] == 0) q.push(i);
	}
	topological_sort();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j < N; j++) {
			char x;
			cin >> x;
			if (x == '>') {
				connect[(i - 1) * N + j + 1].push_back((i - 1) * N + j);
				Step[(i - 1) * N + j]++;
			}
			else {
				connect[(i - 1) * N + j].push_back((i - 1) * N + j + 1);
				Step[(i - 1) * N + j + 1]++;
			}
		}
	}
	for (int i = 1; i < N; i++) {
		for (int j = 1; j <= N; j++) {
			char x;
			cin >> x;
			if (x == '>') {
				connect[i * N + j].push_back((i - 1) * N + j);
				Step[(i - 1) * N + j]++;
			}
			else {
				connect[(i - 1) * N + j].push_back(i * N + j);
				Step[i * N + j]++;
			}
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.