문제

https://school.programmers.co.kr/learn/courses/30/lessons/150366

---

입력

• 실행할 명령어들이 담긴 1차원 문자열 배열 commands

---

출력

• commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return

---

풀이

제한조건

• 1 ≤ commands의 길이 ≤ 1,000

접근방법

Union-Find

명령어들을 살펴보면, 병합을 통해 한 번에 여러 셀의 값을 조정해야 한다.
더불어 병합된 셀을 다시 분리할 수 있어야 한다.

그럼 생각할 수 있는 방법은 2개가 떠오른다.
1. Union-find를 통해 부모 셀을 가지게 만들어 관리하기.
2. Map과 List를 활용해서 매핑을 통해 해결하기 (삼성 B형 스타일)

여기서는 1번 방법으로 진행했다.

우선 최대 R과 C의 범위가 50이다.
union-find에서 parent를 이차원 배열로 관리하면 번거롭다.
1차원으로 압축해주자.

좌표 : r * 50 + c

이제 하나씩 구현해야할 기능을 살펴보자
Case 1. "UPDATE r c value"
r,c의 값을 value로 설정한다.

r,c가 병합되지 않은 셀이라면, r,c자리에 value값을 넣으면 된다.
만약 병합된 셀이라면, find 함수를 통해 부모 위치에 값을 변경해두자.

Case 2. "UPDATE value1 value2"
value1을 가진 셀을 모두 value2로 변경한다.
r과 c의 범위가 크지 않으므로 전체를 순회하며 변경해주도록 하자.

Map자료구조를 통해 특정 값을 가진 셀의 위치를 모두 관리해준다면,
시간적으로 더 효율적으로 구현할 수 있다.

Case 3. "MERGE r1 c1 r2 c2"
r1,c1의 셀과 r2,c2의 셀을 병합한다.
union함수를 통해 부모셀을 합쳐주면 된다.

이때, 아래 항목을 주의하여 union함수를 구현해주자.

• 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다.
• 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다.

Case 4. "UNMERGE r c"
r,c와 연결된 모든 병합을 해제한다.

r,c를 통해 부모셀의 좌표 압축값을 구하고
해당 값을 가지는 모든 셀을 초기화 해주면 된다.

Case 5. "PRINT r c"
r,c의 값을 출력한다.
r,c의 부모셀을 찾아서 값을 출력해주면 된다.

주의
find 함수를 호출해서 부모셀이 어느것인지 갱신해주는 작업을 잊지 말자.
또한 union 과정에서 부모셀의 위치를 갱신해주는 작업을 주의하자.
자식 셀이 병합될 경우, union 함수의 구현에 따라 자식 셀의 parent 값이 갱신되지 않을 수 있다.

---

코드

import java.util.ArrayList;
import java.util.List;

class Solution {
	String[] cellValue;
	int[] parent;
	final int MAX = 50;
	final int MAX_SIZE = MAX * MAX + 1;

	public int find(int n) {
		if (n == parent[n])
			return n;
		return parent[n] = find(parent[n]);
	}

	public void union(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b)
			return;

		if (cellValue[a].equals("") && !cellValue[b].equals("")) {
			parent[a] = b;
			cellValue[a] = "";
		} else {
			parent[b] = a;
			cellValue[b] = "";
		}
        
        // 자식 셀의 parent가 갱신되지 않을 수 있다.
		for(int i = 0 ; i < MAX_SIZE; ++i)
			find(i);
	}

	// 좌표 압축
	public int getIndex(String r, String c) {
		return (Integer.parseInt(r) - 1) * MAX + Integer.parseInt(c) - 1;
	}

	public String[] solution(String[] commands) {
		cellValue = new String[MAX_SIZE];
		parent = new int[MAX_SIZE];
		List<String> answer = new ArrayList<>();

		for (int i = 0; i < MAX_SIZE; ++i) {
			cellValue[i] = "";
			parent[i] = i;
		}

		for (String command : commands) {
			String[] inputs = command.split(" ");
			if (inputs[0].equals("UPDATE")) {
				if (inputs.length == 4) {
					// Case 1. "UPDATE r c value"
					int idx = getIndex(inputs[1], inputs[2]);
					cellValue[find(idx)] = inputs[3];
                    
				} else {
					// Case 2. "UPDATE value1 value2"
					for (int i = 0; i < MAX_SIZE; ++i)
						if (cellValue[i].equals(inputs[1]))
							cellValue[i] = inputs[2];
				}
                
			} else if (inputs[0].equals("MERGE")) {
				// Case 3. "MERGE r1 c1 r2 c2"
				int idx = getIndex(inputs[1], inputs[2]);
				int other = getIndex(inputs[3], inputs[4]);
				union(idx, other);
                
			} else if (inputs[0].equals("UNMERGE")) {
				// Case 4. "UNMERGE r c"
				int idx = getIndex(inputs[1], inputs[2]);
				int parentIdx = find(idx);
				String base = cellValue[parentIdx];
				for (int i = 0; i < MAX_SIZE; ++i) {
					if (parent[i] == parentIdx) {
						parent[i] = i;
						cellValue[i] = "";
					}
				}
				cellValue[idx] = base;
                
			} else { // PRINT
				// Case 5. "PRINT r c"
				int idx = getIndex(inputs[1], inputs[2]);
				int findIdx = find(idx);
				if (cellValue[findIdx].equals(""))
					answer.add("EMPTY");
				else
					answer.add(cellValue[findIdx]);
			}
		}
		return answer.toArray(new String[answer.size()]);
	}
}