BOJ 2273번 줄 서기

BOJ : www.acmicpc.net/problem/2273

2273번: 줄 서기

 

문제

N명의 학생들이 키 순서대로 줄을 서려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 각 학생이 설 수 있는 위치의 범위를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1≤N≤256), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 같은 학생들을 여러 번 비교했을 수도 있다.

 

출력

N개의 줄에 각 학생이 설 수 있는 위치의 범위를 출력한다. 불가능한 경우에는 첫째 줄에 -1을 출력한다.

 

 

풀이

요즘 문제 풀기가 바빠 포스팅을 잘 안했는데, 이번 문제는 내가 코드를 꼼꼼히 작성하지 않는다는 것과 아무 생각없이 문제를 접근한다는거에 대한 반성의 의미로 포스팅하게 되었다.

이미 비교되어 있는 정점에서 서로 다른 정점과의 비교값을 얻기 위한 이와 같은 문제는 플로이드 와샬로 접근해야한다.

 

처음에는 플로이드와샬로 접근해놓고 모든 조합을 구하기 위해 DFS를 사용했는데,, 왜그런거야..

이 문제의 해결법은 나보다 키가 작은사람, 키가 큰사람의 인원수만 구하면 되는건데........

현재 학생과 다른 학생들 간의 대소관계를 비교하는 플로이드 과정이 끝나면

현재 학생이 가질 수 있는 범위는 다음과 같아진다

left : 1, right : N 일때

나보다 큰 학생이 있는 경우 left+1

나보다 작은 학생이 있는 경우 right-1

이렇게 간단하게 범위를 계산할 수 있게 된다

 

#include <iostream>
using namespace std;
int arr[257][257], N, M, s, e, l, r;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> M;
	
	for (int i = 0; i < M; i++) {
		cin >> s >> e;
		if (arr[s][e] == -1 || arr[e][s] == 1) {
			cout << "-1";
			return 0;
		}
		arr[s][e] = 1;
		arr[e][s] = -1;
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i == j) continue;
				if (arr[i][j] != 0) {
					if ((arr[i][j] == arr[j][i]) || (arr[i][k] == 1 && arr[k][j] == 1 && (arr[i][j] == -1 || arr[j][i] == 1)) || (arr[i][k] == -1 && arr[k][j] == -1 && (arr[i][j] == 1 || arr[j][i] == -1))) {
						cout << "-1";
						return 0;
					}
				}
				if (arr[i][j] == 0) {
					if (arr[i][k] == arr[k][j]) {
						arr[i][j] = arr[i][k];
						arr[j][i] = -arr[i][j];
					}
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		l = 1, r = N;
		for (int j = 1; j <= N; j++) {
			if (arr[i][j] == 1) r--;
			else if (arr[i][j] == -1) l++;
		}
		cout << l << " " << r << "\n";
	}
}