문제
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150366
풀이
핵심은 Union-Find 알고리즘을 활용해 MERGE를 처리하는 것 입니다.
초기화 부분:
static int n = 2500; // 50*50
static int grp[]; // 그룹. 처음에 각 그룹 대표는 자기 자신.
static String values[]; // 값
public String[] solution(String[] commands) {
grp = new int[n];
values = new String[n];
List<String> answers = new ArrayList<>();
for(int i = 0; i < n; i++){
grp[i] = i; // 처음에 각 인덱스의 그룹 대표는 자기 자신으로 초기화.
}Union, Find 함수 :
static int find(int idx){
if(idx == grp[idx]){
return idx;
}
//그룹 대표 갱신
return grp[idx] = find(grp[idx]);
}
static void union(int g1, int g2){
g1 = find(g1);
g2 = find(g2);
//이미 같은 그룹일 경우 바로 리턴
if(g1 == g2){
return;
}
//g1을 대표로 두 그룹을 병합
values[g2] = null;
grp[g2] = g1;
}50x50의 표를 이중배열이 아닌 2500 크기의 단일 배열로 사용했습니다.
ex) 4번째 줄의 50번째 칸 인덱스 -> (4 - 1) * 50 + (50 - 1) = 199
이제 command를 switch를 통해 하나씩 처리해 봅니다.
1. UPDATE
case "UPDATE" :
String v1 = st.nextToken();
String v2 = st.nextToken();
if(st.hasMoreTokens()){ // 인자가 4개면
String value = st.nextToken();
r = Integer.parseInt(v1) - 1;
c = Integer.parseInt(v2) - 1;
values[find(r * 50 + c)] = value;
}
else{ // 인자가 3개면
for(int j = 0; j < n; j++){
if(values[find(j)] != null && values[find(j)].equals(v1)){
values[find(j)] = v2;
}
}
}
break;UPDATE 부분입니다.
인자 갯수에 따라 선택한 위치의 셀 값이나 특정 값을 가지고 있는 모든 셀의 값을 업데이트합니다.
유의점은 셀을 탐색할 때 find함수를 통해 병합된 셀 그룹의 대표를 찾아야 하는 것 입니다.
2. MERGE
case "MERGE" :
int r1 = Integer.parseInt(st.nextToken()) - 1;
int c1 = Integer.parseInt(st.nextToken()) - 1;
int r2 = Integer.parseInt(st.nextToken()) - 1;
int c2 = Integer.parseInt(st.nextToken()) - 1;
int num1 = r1*50 + c1;
int num2 = r2*50 + c2;
//둘 중 하나만 값을 가지고 있는 경우
if(values[find(num1)] == null && values[find(num2)] != null){
int temp = num1;
num1 = num2;
num2 = temp;
}
union(num1, num2);
break;MERGE 부분입니다.
선택된 두 셀을 union함수를 이용해 병합합니다.
유의점은 두 셀이 모두 값을 가지고 있는 경우 앞 셀의 값으로, 둘 중 하나만 값을 가지고 있는 경우 그 값으로 병합된 셀의 값을 세트해줘야 한다는 것 입니다.
3. UNMERGE
case "UNMERGE" :
r = Integer.parseInt(st.nextToken()) - 1;
c = Integer.parseInt(st.nextToken()) - 1;
int g = find(r*50 +c); // 셀이 소속된 그룹
v = values[g];
for(int j = 0; j < n; j++){ //*! 모든 셀의 그룹 대표를 갱신하기 위해.
find(j);
}
for(int j = 0; j < n; j++){
if(find(j) == g){ // 해당 그룹에 속해 있으면 unmerge
grp[j] = j;
if(j == r*50 + c){
values[j] = v;
}else{
values[j] = null;
}
}
}
break;UNMERGE 부분입니다.
단순하게 표를 순회하며 선택된 셀과 같은 그룹이면 grp[셀i] = 셀i을 통해 그룹을 초기화하고 값을 null로 바꿉니다. 선택된 셀일 경우에는 값을 유지합니다.
어렵지 않은 문제라고 생각했다가 가장 고생한 부분입니다.
find함수를 통해 그룹 대표를 갱신 하지 않은 셀이 있는데 중간에 그룹을 해제해 주면 문제가 생깁니다.
ex) grp[a] = b, grp[b] = c 같이 a -> b -> c 의 형태이고 c그룹을 해제하려 할 때, b를 먼저 그룹 해제해 버리면 a가 c 그룹이라는 걸 알 수가 없어서 그룹 해제 대상에서 벗어남
간단하게 그룹 해제 전에 모든 셀의 그룹을 find를 통해 업데이트 해주면 해결됩니다.
셀 개수가 2500개 밖에 안되서 간단했지만 더 좋은 방법이 있을 거 같긴 하네요.
4. PRINT
마지막으로 PRINT를 통해 해당 셀의 값을 배열에 넣어주면 됩니다.
문제 자체는 Union-Find 알고리즘을 알고 있다면 어렵지 않은 문제였지만 구현해야 할 부분이 다소 많다보니 실수하기 쉬운 부분이 많았습니다.
전체 코드
import java.util.*;
class Solution {
static int n = 2500;
static int grp[];
static String values[];
public String[] solution(String[] commands) {
grp = new int[n];
values = new String[n];
List<String> answers = new ArrayList<>();
for(int i = 0; i < n; i++){
grp[i] = i;
}
StringTokenizer st;
for(int i = 0; i < commands.length; i++){
st = new StringTokenizer(commands[i]);
int r, c;
String v;
switch(st.nextToken()){
case "UPDATE" :
String v1 = st.nextToken();
String v2 = st.nextToken();
if(st.hasMoreTokens()){
String value = st.nextToken();
r = Integer.parseInt(v1) - 1;
c = Integer.parseInt(v2) - 1;
values[find(r * 50 + c)] = value;
}
else{
for(int j = 0; j < n; j++){
if(values[find(j)] != null && values[find(j)].equals(v1)){
values[find(j)] = v2;
}
}
}
break;
case "MERGE" :
int r1 = Integer.parseInt(st.nextToken()) - 1;
int c1 = Integer.parseInt(st.nextToken()) - 1;
int r2 = Integer.parseInt(st.nextToken()) - 1;
int c2 = Integer.parseInt(st.nextToken()) - 1;
int num1 = r1*50 + c1;
int num2 = r2*50 + c2;
if(values[find(num1)] == null && values[find(num2)] != null){
int temp = num1;
num1 = num2;
num2 = temp;
}
union(num1, num2);
break;
case "UNMERGE" :
r = Integer.parseInt(st.nextToken()) - 1;
c = Integer.parseInt(st.nextToken()) - 1;
int g = find(r*50 +c);
v = values[g];
for(int j = 0; j < n; j++){
find(j);
}
for(int j = 0; j < n; j++){
if(find(j) == g){
grp[j] = j;
if(j == r*50 + c){
values[j] = v;
}else{
values[j] = null;
}
}
}
break;
case "PRINT" :
r = Integer.parseInt(st.nextToken()) - 1;
c = Integer.parseInt(st.nextToken()) - 1;
v = values[find(r*50 + c)];
answers.add(v == null ? "EMPTY" : v);
break;
}
}
String[] answer = new String[answers.size()];
for(int i = 0; i < answers.size(); i++){
answer[i] = answers.get(i);
}
return answer;
}
static int find(int idx){
if(idx == grp[idx]){
return idx;
}
return grp[idx] = find(grp[idx]);
}
static void union(int g1, int g2){
g1 = find(g1);
g2 = find(g2);
if(g1 == g2){
return;
}
values[g2] = null;
grp[g2] = g1;
}
}