(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을 진행한다.

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

 

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

 

 

 

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

 

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

 

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

 

 

감사합니다!

 

 

소스코드

---

	package disjointSet;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	// 여행 가자
	// Disjoint - Set ?
	public class p1976 {
	static int[][] map;
	static ArrayList<Integer>[] graph;
	static ArrayList<Integer> route;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int n = Integer.parseInt(st.nextToken());
	int m = Integer.parseInt(br.readLine());
	route = new ArrayList<Integer>();
	graph = new ArrayList[n + 1];
	for(int i = 1; i <= n; i++) {
	graph[i] = new ArrayList<Integer>();
	}
	// Input 넣기
	for(int i = 1; i <= n; i++) {
	st = new StringTokenizer(br.readLine());
	for(int j = 1; j <= n; j++) {
	int num = Integer.parseInt(st.nextToken());
	if(num == 1) {
	graph[i].add(j);
	}
	}
	}
	st = new StringTokenizer(br.readLine());
	while(st.hasMoreTokens()) {
	int dest = Integer.parseInt(st.nextToken());
	route.add(dest);
	}
	String print = possibleRoute(n, route.get(0)) ? "YES" : "NO";
	System.out.println(print);
	}
	static boolean possibleRoute(int n, int start) {
	boolean[] visited = new boolean[n + 1];
	Queue<Integer> q = new LinkedList<Integer>();
	q.offer(start);
	while(!q.isEmpty()) {
	int ele = q.poll();
	if(visited[ele]) {
	continue;
	}
	visited[ele] = true;
	for(int i = 0; i < graph[ele].size(); i++) {
	int next = graph[ele].get(i);
	q.offer(next);
	}
	}
	// 경로에 한 번이라도 방문한 적이 있는지 파악하기
	// 중복 경로가 가능하고, 이전 길로도 되돌아갈 수 있어서 한 번이라도 방문했으면 어떤 순서건 간에 방문할 수 있다.
	for(int dest : route) {
	if(visited[dest]) {
	continue;
	}
	return false;
	}
	return true;
	}
	}

view raw p1976.java hosted with ❤ by GitHub

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	// 방 청소
	// Union - Find
	public class p9938 {
	static boolean[] checked;
	static int[] drawerParent;
	static StringBuilder sb;
	public static void main(String args[]) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int n = Integer.parseInt(st.nextToken());
	int l = Integer.parseInt(st.nextToken());
	checked = new boolean[l + 1]; // 1 ~ L
	drawerParent = new int[l + 1];
	sb = new StringBuilder();
	// parent 노드 초기화
	for(int i = 1; i <= l; i++) {
	drawerParent[i] = i;
	}
	for(int i = 1; i <= n; i++) {
	st = new StringTokenizer(br.readLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	if(!checked[a]) { // 1번 조건 : 서랍 a가 비어있는 경우
	checked[a] = true;
	union(a, b);
	}
	else if(!checked[b]) { // 2번 조건 : 서랍 b가 비어있는 경우
	checked[b] = true;
	union(b, a);
	}
	else if(!checked[find(a)]) { // 3번 조건 : 서랍 a에 술병이 있는 경우
	checked[find(a)] = true;
	union(a, b);
	}
	else if(!checked[find(b)]) { // 4번 조건 : 서랍 b에 술병이 있는 경우
	checked[find(b)] = true;
	union(b, a);
	}
	else {
	sb.append("SMECE").append("\n");
	}
	}
	System.out.println(sb.toString());
	}
	static void union(int a, int b) {
	a = find(a);
	b = find(b);
	drawerParent[a] = b;
	sb.append("LADICA").append("\n");
	}
	static int find(int index) {
	if(drawerParent[index] == index) {
	return index;
	}
	return drawerParent[index] = find(drawerParent[index]);
	}
	}

view raw p9938.java hosted with ❤ by GitHub