[코딩테스트][백준] 🔥 백준 9938번 "방 청소" 문제: Java으로 완벽 해결하기! 🔥

문제 링크

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

🛠️ 미해결

• 풀이시간 : 2시간 이상
• 도저히 왜 틀렸는지 모르겠다... : 이론 상의 설계로 깔끔하다고 느꼈는데 틀렸다... 이유를 알 수가 없다. GPT로 반례나 코드에 대해 틀린점을 지적해달라고 해도 깔끔한 설명을 듣지 못하였다.
• 내 풀이의 설명 : 내 이론은 이러하다. 술병을 서랍에 숨기기 때문에 바로 다음 비어있는 서랍을 찾기 위해서는 전체 서랍이 비었는지를 빠르게 체크할 수 있어야하고 마치 백준의 항공 문제처럼 실제의 L보다 L+1의 지점에 다 서랍이 꽉 찼을 때 방문되는 것을 하나 두는 것이다. 그렇게 자기보다 +1인 서랍과 연결되고 만약 자기 자신과 자기 자신의 부모가 같다면 그 서랍은 비어있기 때문에 그 서랍을 채워넣으면 된다. 라는게 내 논리인데 왜 틀렸는지 모르겠다... 계속 4%에서 틀린다...

내 풀이

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static int findParent(int[] parent, int x){
        if(parent[x]!=x){
            parent[x]=findParent(parent,parent[x]);
        }
        return parent[x];
    }

    public static void unionParent(int[] parent,int a,int b){
        a=findParent(parent,a);
        b=findParent(parent,b);
        if(a>b){
            parent[b]=a;
        }else{
            parent[a]=b;
        }
    }
    
    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 L=Integer.parseInt(st.nextToken());

        int[] parent=new int[L+2];
        for(int i=1;i<L+2;i++){
            parent[i]=i;
        }

        StringBuilder sb=new StringBuilder();

        for(int i=0;i<N;i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            int parentA=findParent(parent,a);
            int parentB=findParent(parent,b);
            int emptyL=findParent(parent,1);
            if(parentA==a){
                unionParent(parent,a,a+1);
                sb.append("LADICA\n");
            }else if(parentB==b){
                unionParent(parent,b,b+1);
                sb.append("LADICA\n");
            }else if(emptyL!=L+1){
                unionParent(parent,emptyL,emptyL+1);
                sb.append("LADICA\n");
            }else{
                sb.append("SMECE\n");
            }
        }
        
        System.out.println(sb.toString());
    }
}

정답 풀이

import java.util.*;
import java.io.*;

public class Main {
    static int[] parent;
    static boolean[] chk;

    public static int findParent(int x) {
        if (parent[x] != x) {
            parent[x] = findParent(parent[x]);
        }
        return parent[x];
    }

    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a != b) {
            parent[a] = b;
        }
    }

    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 L = Integer.parseInt(st.nextToken());

        parent = new int[L + 1];
        chk = new boolean[L + 1];

        for (int i = 1; i <= L; i++) {
            parent[i] = i;
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            int pa = findParent(a);
            if (!chk[pa]) {
                chk[pa] = true;
                unionParent(pa, b);
                sb.append("LADICA\n");
            } else {
                int pb = findParent(b);
                if (!chk[pb]) {
                    chk[pb] = true;
                    unionParent(pb, a);
                    sb.append("LADICA\n");
                } else {
                    sb.append("SMECE\n");
                }
            }
        }

        System.out.print(sb.toString());
    }
}