[Programmers] 표 병합

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/150366

프로그래머스

 

유니온 파인드를 이용하는 문제였으며 지문에서 주어진 대로 구현하면 되는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 우선 board 이차원 배열을 모두 "EMPTY"로 초기화하고 coord2coord key-value를 모두 각 좌표로 초기화합니다.

1.1 여기서 coord2coord가 유니온 파인드에 사용되는 map이며 key는 좌표 value는 집합의 루트 좌표입니다.

2. 문자열 전처리를 할 때 stringstream을 이용하여 공백 단위로 끊어서 읽습니다.

2.1 value1, value2가 모두 숫자로 이루어지는 케이스도 있는 것으로 추정되어 istringstream 대신 stringstream으로 처리하는 것을 추천드립니다.

3. 주어진 명령어를 기반으로 지문에서 주어진 대로 구현을 합니다.

3.1 UPDATE 명령어는 두 가지 타입으로 나뉘므로 stringstream으로 문자열을 전처리했을 때 문자열이 4개인지 3개인지 판별합니다.

3.1.1 UPDATE r c value 명령어일 경우 coord2coord map을 통해 {r, c}의 루트 좌표를 찾아 해당 좌표의 값을 value로 업데이트합니다.

3.1.2 UPDATE value1 value2 명령어일 경우 board를 순회하며 value1인 좌표를 value2로 업데이트합니다.

3.2 MERGE 명령어는 주어진 {r, c}와 {r2, c2} 각각의 루트 좌표를 찾은 뒤 병합을 해줍니다.

3.2.1 두 좌표가 같은 집합에 속할 경우 예외처리를 하고

3.2.2 {r, c} 집합의 value가 "EMPTY"이지만 {r2, c2} 집합의 value가 "EMPTY"가 아닌 경우 예외처리를 해줘야 합니다.

3.3 UNMERGE 명령어의 경우 {r, c}에만 현재 집합의 값을 갖고 나머지 좌표들은 다시 초기화해 줍니다.

3.4 PRINT 명령어의 경우 {r, c}의 루트 좌표를 찾아 해당 좌표의 값을 answer 벡터에 추가해 줍니다.

4. 주어진 commands에 대해 2~3번을 반복한 뒤 answer 벡터를 반환합니다.

 

 

개발환경: Programmers IDE 

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

 

추가 테스트 케이스 (질문 게시판 참고)

 

input

• ["UPDATE 1 1 menu", "MERGE 1 1 1 2", "MERGE 1 1 1 3", "MERGE 1 1 1 4", "MERGE 1 2 1 3", "UPDATE 1 1 hansik", "PRINT 1 1", "PRINT 1 2", "PRINT 1 3", "PRINT 1 4"]

 

output

• ["hansik", "hansik", "hansik", "hansik"]

 

input

• ["UPDATE 1 1 A", "UPDATE 2 2 B", "UPDATE 3 3 C", "UPDATE 4 4 D", "MERGE 1 1 2 2", "MERGE 3 3 4 4", "MERGE 1 1 3 3", "UNMERGE 1 1", "PRINT 1 1", "PRINT 2 2", "PRINT 3 3", "PRINT 4 4"]

 

output

• ["A", "EMPTY", "EMPTY", "EMPTY"]

 

input

• ["MERGE 1 1 2 2", "MERGE 1 1 3 3", "UPDATE 3 3 A", "PRINT 1 1", "PRINT 2 2", "PRINT 3 3"]

 

output

• ["A", "A", "A"]