Point 인스턴스를 2개 가지고 있는, Line 클래스를 정의했습니다. equals 메소드는 Point 의 내용들이 모두 같으면 true, 다르면 false 를 반환하도록 Point 클래스의 equals 메소드를 이용했습니다. showPosition, change 메소드는 인스턴스 변수의 값을 출력해주고, 값을 바꿔주는 메소드입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
publicclass test{
publicstaticvoid main(String args[]) {
Line line1 =new Line(new Point(5, 7), new Point(3, 4));
오늘은 자바 최상위 클래스 Object 클래스의 equals 메소드에 대해서 알아보겠습니다.
equals 메소드
Object 클래스에는 다음과 같이 equals 메소드가 정의되어있습니다.
public boolean equals(Object obj)
메소드 이름 그대로 같은지 다른지 판단해서 boolean 값을 return 해주는 메소드로, 오버라이딩을 통해 원하는 내용 비교를 할 수 있도록 최상위 클래스인 Object 클래스에 정의되어 있습니다.
우리가 비교를 생각하면 "==" 연산이 가장 먼저 떠오릅니다. 하지만, "==" 연산은 참조대상이 같은지, 다른지 판단해주는 연산으로 우리가 원하는 내용 비교와는 조금 다릅니다.
같은 문자열을 담고 있는 2개의 String 인스턴스를 생성해 보도록 하겠습니다.
public class test{
public static void main(String args[]) {
String name1 = new String("travelbeeee");
String name2 = new String("travelbeeee");
if(name1 == name2) System.out.println("둘이 같습니다");
else System.out.println("둘이 다릅니다");
}
}
name1, name2 인스턴스에는 분명히 같은 문자열이 저장되어있지만, 각각 인스턴스를 생성했기 때문에 서로 다른 인스턴스를 참조하고 있습니다. 따라서, "==" 연산의 결과는 둘이 다르다고 판단합니다.
[Output]
둘이 다릅니다
그럼 내용 비교를 하고 싶으면 어떻게 해야 될까요? 그럴 때 equals 메소드를 오버라이딩해서 사용하면 됩니다. String 클래스에서는 이미 equals 메소드를 오버라이딩해서 지원해주고 있기 때문에, 다음과 같이 사용하면 됩니다.
public class test{
public static void main(String args[]) {
String name1 = new String("travelbeeee");
String name2 = new String("travelbeeee");
if(name1.equals(name2)) System.out.println("둘이 내용이 같습니다");
else System.out.println("둘이 내용이 다릅니다");
}
}
[Output]
둘이 내용이 같습니다
x좌표와 y좌표를 담고 있는 클래스를 만든 후, equals 메소드를 좌표가 같은지 판단해주도록 오버라이딩 해보겠습니다.
class Point{
private int xPos;
private int yPos;
public Point(int x, int y) {
xPos = x;
yPos = y;
}
@Override
public boolean equals(Object obj) {
if(((Point)obj).xPos == xPos && ((Point)obj).yPos == yPos) return true;
return false;
}
}
public class test{
public static void main(String args[]) {
Point p1 = new Point(5, 7);
Point p2 = new Point(5, 7);
if(p1 == p2)
System.out.println("참조대상이 같다");
else
System.out.println("참조대상이 다르다");
if(p1.equals(p2))
System.out.println("내용이 같다");
else
System.out.println("내용이 다르다");
}
}
[Output]
참조대상이 다르다
내용이 같다
"==" 연산 결과는 서로 다른 인스턴스를 참조하고 있다고 알려주고 있지만, equals 메소드를 둘의 좌표를 비교하도록 오버라이딩 했기 때문에 내용이 같다고 비교해주고 있는 것을 볼 수 있습니다.
이렇듯 두 인스턴스의 내용 비교 결과인 true, false 의 반환 조건은 해당 클래스를 정의하는 프로그래머가 결정해야 합니다. 기본적으로 Object 클래스의 equals 메소드는 "==" 연산자와 마찬가지로 참조변수의 참조 값을 비교하도록 정의되어 있습니다. 하지만, "==" 연산이 참조변수의 참조 값을 비교하는 기능을 지원해주므로 String 클래스 등과 같이 자바에서 제공하는 표준 클래스의 경우 equals 메소드가 내용 비교를 하도록 이미 오버라이딩 되어 있는 경우가 많습니다.
a 동영상과 b 동영상의 relevant 값은 a에서 b로 가는 경로 중 간선의 값이 가장 작은 값이 됩니다. 우리는 k와 v가 주어질 때마다, v번 동영상에서 다른 모든 동영상까지 relevant 값이 k 이상인 동영상들을 count 해줘야합니다. 따라서, a 동영상에서 시작해서 BFS 탐색을 진행하면서 다른 모든 동영상과의 relevant 값을 구하면 되는데, a에서 어떤 동영상까지 탐색하는데 relevant 값이 주어진 k보다 작아진다면, 그 뒤의 탐색들도 다 k보다 relevant 값이 작아지므로 탐색을 마저 진행하지 않는다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int N, Q, p, q, r, k, v;
vector<pair<int, int>> map[5001];
int BFS(int k, int v) {
int ans = 0;
vector<bool> visited(5001, false);
queue<int> q;
q.push(v);
visited[v] = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = 0; i < map[cur].size(); i++) {
int next = map[cur][i].first;
int relev = map[cur][i].second;
if (!visited[next] && k <= relev) {
visited[next] = 1;
q.push(next);
ans++;
}
}
}
return ans;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> N >> Q;
for (int i = 0; i < N - 1; i++) {
cin >> p >> q >> r;
map[p].push_back({ q, r });
map[q].push_back({ p, r });
}
for (int i = 0; i < Q; i++) {
cin >> k >> v;
cout << BFS(k, v) << '\n';
}
return 0;
}
N개의 노드가 존재하고, a 노드에서 b 노드로 가는 간선이 존재하려면, 거리가 C 이상이여야 됩니다. 우리는 모든 노드들이 서로 연결되어있는 상태를 최소 비용으로 만들고 싶으므로, MST를 만들면 됩니다.
MST 알고리즘은 대표적으로 Prim, Kruskal 2개가 있는데 이 문제는 간선이 굉장히 많이 존재할 수 있는 밀집 그래프 문제이므로 Kruskal로 MST를 구하면 시간초과를 직면하게 되고, Prim 알고리즘을 사용해야된다.
1) 모든 노드를 순회하며 거리를 계산하고, 거리가 C 이상이면 graph 에 간선을 만들어준다.
( 간선은 양방향 )
2) Prim 알고리즘을 통해 MST를 구한다.
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
const int INF = 1000000001;
int N, C;
int graph[2000][2000];
pair<int, int> point[2000];
int dist[2000];
bool selected[2000];
int getDist(int i, int j) {
return (int)pow(point[i].first - point[j].first, 2) + (int)pow(point[i].second - point[j].second, 2);
}
int get_min_vertex() {
int v;
for (int i = 0; i < N; i++) {
if (!selected[i]) {
v = i;
break;
}
}
for (int i = 0; i < N; i++)
if (!selected[i] && (dist[i] < dist[v])) v = i;
return v;
}
int prim(int s) {
for (int i = 0; i < N; i++)
dist[i] = INF;
dist[s] = 0;
for (int i = 0; i < N; i++) {
int u = get_min_vertex();
selected[u] = 1;
if (dist[u] == INF) return -1;
for (int j = 0; j < N; j++)
if (graph[u][j] != INF && !selected[j] && graph[u][j] < dist[j])
dist[j] = graph[u][j];
}
int ans = 0;
for(int i = 0; i < N; i++) ans += dist[i];
return ans;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// i <--> j 의 모든 edge를 구하고, MST를 구하면 된다.
cin >> N >> C;
for (int i = 0; i < N; i++)
cin >> point[i].first >> point[i].second;
// 프림으로 해보자.
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++) {
int dist = getDist(i, j);
if (C <= dist) graph[i][j] = graph[j][i] = dist;
else graph[i][j] = graph[j][i] = INF;
}
cout << prim(0) << '\n';
return 0;
}
