(JAVA) 백준 9938번 : 방 청소

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

9938번: 방 청소

 

너무 이해가 되지 않아

 

풀이를 참고한 문제.

 

난이도는 좀 높다.

 

 

이게 생각을 살짝 바꾸면 해결할 수 있는데 그게 어렵다.

 

 

그리고 문제에서

 

형광칠한 부분이 조금 이해가 안됬었다.

 

 

  -  만약 Union - Find 알고리즘을 사용해야 한다면 술을 다른 서랍으로 이동시키기 위해 parent를 어떻게 설정할 건지

  -  술을 서랍에 넣었을 때를 체크해두는 방법

 

 

이렇게 두 가지를 해결못해 풀이 참고를 했었다.

 

 

 

핵심은

 

 

  -  서랍에 술을 넣었는지 여부를 파악하기 위해 boolean 배열 생성해서 관리한다.

 

 

  -  술을 해당 서랍에 넣을 때, parent는 넣지 않은 다른 서랍 번호를 술을 넣은 서람의 parent로 설정한다.

    즉, A 서랍에 술을 넣으면 parent[A] = B 가 되고, B 서랍에 술을 넣으면 parent[B] = A 가 된다.

 

    *** 아래에도 적혀있지만, 술을 넣은 서랍의 parent를 적용시키는 이유는 그 서랍에 새로운 술을 넣으려고하면 이전 술을 옮겨야하니까 옮길 다음 서랍을 파악해두기 위함이다.

 

 

  -  따라서, 조건 3과 4를 위해 술을 옮기는 과정은 Find()로 해결할 수 있다.

    Find()로 점핑하다보면 결국 비어있는 노드를 발견할 수 있다.

    A에서 발견 못하면 B에서도 동일하게 진행한다.

 

 

  -  조건 1, 2, 3, 4 모두 술을 넣은 다음 union을 진행한다.

    그래야 해당 서랍에 새로운 술이 들어왔을 때 이전 술을 점핑시킬 다른 서랍을 알 수 있다.

 

    *** 중요한 점은 술을 다른 서랍으로 옮기더라도 결국에 새로운 술이 처음 서랍에 들어가기 때문에 한 번 서랍에 술을 넣으면 절대 사라지지 않는 것과 같다.

 

 

 

위 핵심이 곧 매커니즘이기 때문에

 

별도 매커니즘은 작성하지 않고

 

바로 소스코드를 첨부하겠습니다.

 

 

감사합니다!

 

 

소스코드

---