Algorithm, boj, 돌 그룹(12886)
배운점
- 큐에 배열형태도 넣을수있다
- hashset을 이용하면, 중복된 값을 체크할수있다.
- 규칙을 만들려면 기준값이 필요하다. 여기서는 오름차순으로 정리하는 기준을 가지고 문제풀 수 있다.
풀이
1. 오름 차순으로 정리한후 입력 받은 배열을 큐에 넣는다.
2. 큐에서 배열 하나를 뺀다.
3-1. 첫번째 값이 무조건 제일 작으므로 배열 두개를 새로 만들 수 있다.
arr[1]*2, arr[2]-arr[1], arr[3]
arr[1]*2, arr[2], arr[3]-arr[1]
3-2. 오름 차순으로 정리
4. 새로 만든 배열이 이전에 만든적이 있는지 HashSet을 이용하여 확인해준다.
5. 이전에 만든적이 없으면 Queue에 해당 배열을 넣어준다
6. 2~5반복.
핵심
- 한가지 상황에 대해서 상황이 어떻게 바뀔수 있는지를 알아야 한다.
- 바뀐 상황이 새로운 상황이면 큐에 삽입
코드
package org.baekjoon;
import java.util.*;
public class test12886_ston {
static Queue<int[]> q;
static HashSet<String> hs;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] stone = new int[3];
int sum = 0;
for (int i = 0; i < 3; i++) {
stone[i] = sc.nextInt();
sum += stone[i];
}
if (sum % 3 != 0)
System.out.println(0);
else {
Arrays.sort(stone);
q = new LinkedList<>();
hs = new HashSet<>();
q.offer(stone);
bfs();
}
}
private static void bfs() {
while (!q.isEmpty()) {
int[] stone = q.poll();
// 셋이 같으면 끝.
if (stone[0] == stone[1] && stone[1] == stone[2]) {
System.out.println("1");
return;
}
for (int i = 1; i < 3; i++) {
int[] newStone = stone.clone();
newStone[i] = stone[i] - stone[0];
newStone[0] = stone[0] * 2;
Arrays.sort(newStone);
String str = "";
for (int j = 0; j < 3; j++)
str += newStone[j] + "";
// 해당 패턴이 처음 이면 큐와 해쉬셋에 입력한다
if (!hs.contains(str)) {
q.offer(newStone);
hs.add(str);
}
}
}
System.out.println("0");
}
}