[BOJ] 백준 5588번: 별자리 찾기 _자바(JAVA)

1. 문제

https://www.acmicpc.net/problem/5588

백준 5588번 별자리 찾기

처음엔은 백트래킹으로 모든 별의 좌표 중 m개를 추출한 후 비교했는데,

이러면 시간복잡도가 매우 커져서 시간초과가 발생합니다.

---

2. 접근 및 해결

2-1) 접근

복잡한 연산보다, 해시의 특성을 잘 살리면 풀리는 문제입니다.

여기서 쓰인 해시의 특성은 "동등한 객체는 동일한 해시 코드를 가져야 한다"입니다.

equals()와 hashCode() 메서드는 객체 간의 동등성을 비교하고, 해시 기반의 자료구조에서 객체를 식별하는 데 사용됩니다.

• equals(): 두 객체가 동일한지를 비교합니다. 이 메서드를 사용하여 두 객체가 내용적으로 같은지를 확인할 수 있습니다. 즉, 객체의 내용이 같은 경우 true를 반환하고, 다른 경우 false를 반환합니다.
• hashCode(): 객체의 해시 코드를 반환합니다. 이 해시 코드는 객체를 식별하는 데 사용됩니다. 동일한 객체에 대해 호출된 경우 항상 동일한 해시 코드를 반환해야 합니다.

 

따라서, 선언할 Node객체의 기본 메소드(Object클래스)를 Hash기반에 맞게 변경하여 계산합니다.

 

2-2) 해결

연산에 있어서 핵심코드만 빼오면 아래와 같습니다. 

총 3덩이이고 Main메소드 내의 for문, matchesPattern메소드, Node객체클래스입니다.

 

1.  Main메소드 내의 for문

// **핵심 코드 시작

// Main 메소드
// 모든 별 리스트를 순환하며 Node를 추출
for(Node candidate : allStarAl) {
    // 변환량(deltaX, deltaY) 계산
    int deltaX = candidate.getX() - findStarAl.get(0).getX(); // 전체 별 중, 순서대로 추출한 노드의 X값 - 찾을 별 값의 X값(여기서는 기준 값을 첫 번째 별 값으로 설정) 
    int deltaY = candidate.getY() - findStarAl.get(0).getY();  // 전체 별 중, 순서대로 추출한 노드의 Y값 - 찾을 별 값의 Y값(여기서는 기준 값을 첫 번째 별 값으로 설정)
    if(matchesPattern(deltaX, deltaY)) {  // 패턴 확인
        answerX = deltaX;
        answerY = deltaY;
        break;
    }
}

찾을 별 리스트에서 가장 첫 번째 별 값을 추출했습니다. 기준은 어떤 별이든 상관 없고, 여기서는 첫 번째 별로 잡았습니다.

입력1로 예를 들어보면 들면 찾고 싶은 가장 첫 번째 좌표인 x = 8, y = 5

findStarAl.get(0).getX()는 8, findStarAl.get(0).getY()는 5입니다.

 

candidate.get(x)는 모든 별 리스트에서 하나씩 추출하는 별의 값입니다.

가장 첫 번째 좌표로 예를 들면, x = 10, y =5입니다.

 

따라서, deltaX는 10 - 8 = 2, deltaY는 5 - 5 = 0

여기서 matchesPattern(2, 0)을 실행해봅시다.

 

2. matchesPattern메소드

 찾을 별 리스트(findStarAl)에서 (2, 0)만큼씩 이동했을 때 전체 별 리스트에 대응되는 별들이 있는지를 확인합니다.

만약 대응되지 않으면 해당 좌표는 return false.

// matchesPattern 메소드
static boolean matchesPattern(int deltaX, int deltaY) {
    Set<Node> starSet = new HashSet<>(allStarAl); 
    for(Node star : findStarAl) { // 찾을 별 리스트를 순환하며 Node추출
        // X는 deltaX, Y는 deltaY만큼 이동한 곳에 모든 별 리스트에 해당 좌표가 있는지 확인 
        Node shiftedStar = new Node(star.getX() + deltaX, star.getY()+ deltaY);
        // contains 메서드: HashSet의 contains 메서드는 주어진 객체가 컬렉션에 있는지를 확인
        // 이때 내부적으로 객체의 해시 코드를 기반으로 먼저 검색을 시도하고, 
        // 같은 해시 코드를 가진 객체가 있으면 equals 메서드를 호출하여 내용을 비교
        if(!starSet.contains(shiftedStar)) {
            return false;
        }
    }

    return true;
}

코드자체는 어렵지 않은데 여기서 주의할 점이 있습니다. 바로 HashSet의 contains는 내부적으로 현재 @Override된 메소드를 사용하고 있기 때문이지요! 

어떤걸 @Override하고 있는지 확인해봅시다.

 

3. Node객체클래스

class Node {
	int x, y;
	
	Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	int getX() {
		return this.x;
	}
	
	int getY() {
		return this.y;
	}
	
	// equals() 및 hashCode()를 오버라이드하지 않으면 Java는 기본 Object 클래스의 메서드를 사용
	// 이 메서드들은 객체의 내용이 아닌 참조에 의해 동일한지를 확인(주소값 확인)
	
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Node node = (Node) obj;
        return x == node.x && y == node.y;
    }

    // hasCode 메소드: 해시 코드를 반환하는 메서드
    // 해시 코드는 객체를 해시 테이블에서 검색할 때 사용(해시 집합(HashSet)은 동등한 해시 코드를 가진 객체를 하나로 취급)
    // Object 클래스에 구현되어 있는 기본 hashCode() 메서드는 객체의 메모리 주소를 기반으로 해시 코드를 생성
    // 여기서는 주소가 아니라 값을 기준으로 hashCode를 비교
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

equals와 hashCode가 Override가 되고 있습니다.

Override해주지 않으면, 기본 Object의 equals메소드와 hashCode메소드를 이용하게 됩니다.

기본 Object의 equals, hashCode메소드는 주소 값을 기준으로 비교합니다.

그러나 해시값 자체를 기준으로 비교하도록 해당 메소드들을 변경해두었습니다.

왜냐하면 matchesPattern에서 좌표들을 주소값으로 비교하게 되면 다른 객체이기 때문에 항상 다르게 나오기 때문입니다.

좌표 자체의 값(3, 2)을 확인해주면 시간복잡도가 ArrayList에서 하나씩 빼오는 것보다 n만큼 줄어들게 됩니다.

---

3. 코드(JAVA) 

// 메모리 : 106888KB
// 시간 : 276ms
import java.io.*;
import java.util.*;

// v1: 백트래킹이용 -> 임의의 별 좌표 n개를 뽑아옴 -> 시간초과
// v2: 해시(Hash)의 특성을 이용함
// Hash 값으로 넣을 Node객체 내부에 equals(), hashCode()를 오버라이딩하는 것이 핵심

public class Main {
	static ArrayList<Node> findStarAl, allStarAl; // findStarAl: 찾을 별 리스트, allStarAl: 모든 별 리스트
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		int m = Integer.parseInt(br.readLine());
		findStarAl = new ArrayList<Node>();
	
		// 찾을 별 리스트를 ArrayList에 추가
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			findStarAl.add(new Node(x, y));
		}
		
		int n = Integer.parseInt(br.readLine());
		allStarAl = new ArrayList<Node>();
		
		// 모든 별 리스트를 ArrayList에 추가
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			allStarAl.add(new Node(x, y));
		}
		
		int answerX = 0;
		int answerY = 0;
		
		// **핵심 코드 시작
		// 모든 별 리스트를 순환하며 Node를 추출
		for(Node candidate : allStarAl) {
			// 변환량(deltaX, deltaY) 계산
			int deltaX = candidate.getX() - findStarAl.get(0).getX(); // 전체 별 중, 순서대로 추출한 노드의 X값 - 찾을 별 값의 X값(여기서는 기준 값을 첫 번째 별 값으로 설정) 
			int deltaY = candidate.getY() - findStarAl.get(0).getY();  // 전체 별 중, 순서대로 추출한 노드의 Y값 - 찾을 별 값의 Y값(여기서는 기준 값을 첫 번째 별 값으로 설정)
			if(matchesPattern(deltaX, deltaY)) {  // 패턴 확인
				answerX = deltaX;
				answerY = deltaY;
				break;
			}
		}
		
		bw.write(answerX +" "+answerY);
		br.close();
		bw.close();
	}
	
	// 변환량으로 별자리가 사진속의 별들과 일치하는지 확인
	static boolean matchesPattern(int deltaX, int deltaY) {
		Set<Node> starSet = new HashSet<>(allStarAl); 
		for(Node star : findStarAl) { // 찾을 별 리스트를 순환하며 Node추출
			// X는 deltaX, Y는 deltaY만큼 이동한 곳에 모든 별 리스트에 해당 좌표가 있는지 확인 
			Node shiftedStar = new Node(star.getX() + deltaX, star.getY()+ deltaY);
			// contains 메서드: HashSet의 contains 메서드는 주어진 객체가 컬렉션에 있는지를 확인
			// 이때 내부적으로 객체의 해시 코드를 기반으로 먼저 검색을 시도하고, 
			// 같은 해시 코드를 가진 객체가 있으면 equals 메서드를 호출하여 내용을 비교
			if(!starSet.contains(shiftedStar)) {
				return false;
			}
		}
		
		return true;
	}
}

class Node {
	int x, y;
	
	Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	int getX() {
		return this.x;
	}
	
	int getY() {
		return this.y;
	}
	
	// equals() 및 hashCode()를 오버라이드하지 않으면 Java는 기본 Object 클래스의 메서드를 사용
	// 이 메서드들은 객체의 내용이 아닌 참조에 의해 동일한지를 확인(주소값 확인)
	
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Node node = (Node) obj;
        return x == node.x && y == node.y;
    }

    // hasCode 메소드: 해시 코드를 반환하는 메서드
    // 해시 코드는 객체를 해시 테이블에서 검색할 때 사용(해시 집합(HashSet)은 동등한 해시 코드를 가진 객체를 하나로 취급)
    // Object 클래스에 구현되어 있는 기본 hashCode() 메서드는 객체의 메모리 주소를 기반으로 해시 코드를 생성
    // 여기서는 주소가 아니라 값을 기준으로 hashCode를 비교
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

 

4. 번외_시간초과 코드(JAVA) 

시간초과를 내었던 첫번째 시도 코드

// 시간초과
// 백트래킹을 이용해서 임의의 별 좌표 n개를 뽑아오는 코드
import java.io.*;
import java.util.*;

public class Main {
	static int m, allStarAlSize, answerX, answerY;
	static boolean[] isUsed;
	static ArrayList<Node> findStarAl, findStarDistanceAl, allStarAl, selectedStarAl;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		
		m = Integer.parseInt(br.readLine());
		findStarAl = new ArrayList<Node>();
		allStarAl = new ArrayList<Node>();
		
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			findStarAl.add(new Node(x, y));
		}
		findStarAl.sort(Comparator.comparing(Node::getX).thenComparing(Node::getY));

		// 찾을 m개의 별에 대해 거리 계산
		findStarDistanceAl = new ArrayList<Node>();
		for(int i=1; i<m; i++) {
			int x = findStarAl.get(i).getX()-findStarAl.get(i-1).getX();
			int y = findStarAl.get(i).getY()-findStarAl.get(i-1).getY();
			findStarDistanceAl.add(new Node(x, y));
//			System.out.println(x + " "+ y);
		}
		
		int n = Integer.parseInt(br.readLine());
		
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			allStarAl.add(new Node(x, y));
		}
		allStarAlSize = allStarAl.size();
		isUsed = new boolean[allStarAlSize+1];
		func(0, 0);
		
		bw.write(answerX +" "+answerY);
		br.close();
		bw.close();
	}
	
	static void func(int num, int cnt) {
		if(cnt==m) {
			selectedStarAl = new ArrayList<Node>();
			for(int i=0; i<allStarAlSize; i++) {
				if(isUsed[i]) {
					selectedStarAl.add(allStarAl.get(i));
				}
			}
			if(calcDistance()) return;
		}
		
		for(int i=num; i<allStarAlSize; i++) {
			isUsed[i] = true;
			func(i+1, cnt+1);
			isUsed[i] = false;
		}
		
	}
	
	static boolean calcDistance() {
		selectedStarAl.sort(Comparator.comparing(Node::getX).thenComparing(Node::getY));

		int cnt = 0;
		// select된 n개의 별에 대해 거리 계산
		for(int i=1; i<m; i++) {
			int x = selectedStarAl.get(i).getX()-selectedStarAl.get(i-1).getX();
			int y = selectedStarAl.get(i).getY()-selectedStarAl.get(i-1).getY();
			if((findStarDistanceAl.get(i-1).getX() == x) && (findStarDistanceAl.get(i-1).getY() == y)) {
				cnt++;
			}
		}
		if(cnt==(m-1)) {
//			for(int i=0; i<selectedStarAl.size(); i++) {
//				System.out.println(selectedStarAl.get(i).getX()+" "+selectedStarAl.get(i).getY());
//			}
			answerX = selectedStarAl.get(0).getX() - findStarAl.get(0).getX();
			answerY = selectedStarAl.get(0).getY() - findStarAl.get(0).getY();
			return true;
		}
		return false;
	}
}

---

감사합니다!