[BOJ/JAVA] 백준 10159번 : 저울

10159번: 저울

 

 

 

 

---

 

 

 

• 풀이

 

자신보다 집적접으로 무게가 낮거나 높은 물건을 통해 간접적으로 낮거나 높은 물건을 모두 찾는 문제입니다.

 

이를 풀기 위한 알고리즘은 모든 정점에서 모든 정점의 최단거리를 구하는 플로이드 와샬을 이용했습니다. 플로이드 와샬은 O(N^3)의 시간복잡도를 가지기 때문에 시간을 잘 고려해야합니다. 현재 문제의 N의 최대값은 100으로 100^3은 1000000으로 1초안에 들어오기에 충분한 연산횟수입니다. (참고로 1초에 1억번 정도의 연산을 한다고 생각하시면 됩니다.)

 

해당 문제를 풀기 위해선 자신보다 무게가 많이 나가는 물건과 무게가 적게 나가는 물건을 구별해야합니다. 이유는 예시를 들어보면 1번의 무게보다 낮은 2번과 2번의 무게보다 낮은 3번이 있다고 가정하면 1>2>3>이 될 것 입니다. 하지만 1번의 무게보다 낮은 2번과 2번의 무게보다 높은 3번이 있다고 가정하면 1>2<3 ???? 이 될 것입니다. 그렇기 때문에 본인보다 무게가 높은 것과 무게가 낮은 것을 구별해야합니다.

 

저의 경우에는 a > b의 경우 array[a][b] = 1, array[b][a] = -1로 초기화 하였습니다.

 

이제 플로이드 와샬 알고리즘을 통해, array[i][k]가 0이 아닌 가정하에 array[i][k] == array[k][j]이라면 array[i][j] = array[i][k]로 초기화하며 자신보다 무게가 낮거나 높은 물건을 확인해주었습니다. 즉, i보다 k가 높으면서 k보다 j가 높다면 i보다 j도 높다는 뜻의 알고리즘입니다. (낮은 방식도 마찬가지)

 

위의 플로이드 와샬 알고리즘이 종료가 되면 현재 무게보다 높거나 낮은 모든 물건을 구해줄 수 있을 것 입니다.

 

 

• 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int N, M;
	static StringBuilder sb;	
	static int[][] array;
	
	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);
		
		N = in.nextInt();
		M = in.nextInt();
		sb = new StringBuilder();
		array = new int[N+1][N+1];
		
		for(int i = 0; i < M; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			
			array[a][b] = 1;
			array[b][a] = -1;
		}
		
		for(int k = 1; k <= N; k++) {
			for(int i = 1; i <= N; i++) {
				for(int j =1; j <= N; j++) {
					if (array[i][k] != 0 && array[i][k] == array[k][j]) {
                        array[i][j] = array[i][k];
                    }
				}
			}
		}
		
		for(int i = 1; i <= N; i++) {
			int count = 0;
			for(int j =1; j <= N; j++) {
				if(i == j) continue;
				if(array[i][j] != 0) continue;
				
				count++;
			}
			sb.append(count).append("\n");
		}
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}