백준 [1045] 도로

무난한 최소 스패닝 트리 문제

문제 설명이 좀 난해할 뿐이지, 기본 개념 문제와 별 차이는 없다.

 

 

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

1045번: 도로

 

문제 요약을 하자면 다음과 같다.

i < j 인 간선들 중에서 i가 작은 순으로 나열한다. i 가 같다면, j가 작은 순으로 나열

이 때 모든 도시가 연결되있지 않으면 -1

간선의 수가 M개가 되지 못하면 -1

그 후, 상위 M개의 간선에서 시작점과 끝점의 index 카운팅 후 출력

 

이 문제를 풀면서 실수를 했는데

큐에 간선들을 넣어줄 때, M개만큼 차면 더이상 간선 정보를 처리하지 않았다.

 

여기에 대한 반례

4 3
NYYN
YNYN
YYNY
NNYN

답 : 2 1 2 1

오답 : -1 (간선을 M개만 받게 했을 경우)

물론 간선 정보는 2개만 필요하기에, (0, 1), (0, 2), (2, 3)의 정보만 큐에 들어가고

카운티 역시 2 1 2 1이 된다.

 

하지만, 여기서 문제가 있는데

그 후에 들어오는 (3, 4)를 처리해야 모든 도시가 연결된 걸 나타내는데

이 정보를 누락시켜 모든 도시가 연결되있지 않단 의미로 -1을 반환했다.

 

메모리 사용량 줄여보려다 이런 코너 케이스를 캐치하지 못했다.

 

코드는 접어놨다.

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

class Main {

    static int N, M;
    static char[][] map;
    static int[] roots;
    static Queue<Edge> edges = new LinkedList<>();
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws Exception {
        input();
        solve();
        print();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        roots = new int[N];
        map = new char[N][N];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            roots[i] = i;
            for (int j = i + 1; j < N; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'Y') {
                    edges.add(new Edge(i, j));
                }
            }
        }
    }

    private static void solve() {
        int unionCount = 0;
        int[] count = new int[N];
        if(edges.size() < M) {
            answer.append(-1);
            return;
        }

        Queue<Edge> left = new LinkedList<>();
        while (!edges.isEmpty()) {
            Edge here = edges.poll();
            if (union(here.s, here.e)) {
                count[here.s]++;
                count[here.e]++;
                unionCount++;
            } else {
                left.add(here);
            }
        }
        if (unionCount != N - 1) {
            answer.append(-1);
            return;
        }
        for (int i = N - 1; i < M; i++) {
            if (left.isEmpty()) {
                answer.append(-1);
                return;
            }
            count[left.peek().s]++;
            count[left.peek().e]++;
            left.poll();
        }
        for (int i = 0; i < N; i++) {
            answer.append(count[i]).append(" ");
        }
    }

    private static boolean union(int s, int e) {
        s = find(s);
        e = find(e);

        if(s == e)
            return false;
        else if(s < e)
            roots[e] = s;
        else
            roots[s] = e;
        return true;
    }

    private static int find(int s) {
        if(roots[s] == s)
            return s;
        return roots[s] = find(roots[s]);
    }


    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer.toString());
        bw.flush();
    }
}

class Edge {
    int s, e;

    public Edge(int s, int e) {
        this.s = s;
        this.e = e;
    }
}

 

 

아래 코드는 틀린 코드다.

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

class Main {

    static int N, M;
    static char[][] map;
    static int[] roots;
    static Queue<Edge> edges = new LinkedList<>();
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws Exception {
        input();
        solve();
        print();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        roots = new int[N];
        map = new char[N][N];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            roots[i] = i;
            for (int j = i + 1; j < N; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'Y' && edges.size() < M) {
                    edges.add(new Edge(i, j));
                }
            }
        }
    }

    private static void solve() {
        int unionCount = 0;
        int[] count = new int[N];
        if(edges.size() < M) {
            answer.append(-1);
            return;
        }

        Queue<Edge> left = new LinkedList<>();
        while (!edges.isEmpty()) {
            Edge here = edges.poll();
            if (union(here.s, here.e)) {
                count[here.s]++;
                count[here.e]++;
                unionCount++;
            } else {
                left.add(here);
            }
        }
        if (unionCount != N - 1) {
            answer.append(-1);
            return;
        }
        for (int i = N - 1; i < M; i++) {
            if (left.isEmpty()) {
                answer.append(-1);
                return;
            }
            count[left.peek().s]++;
            count[left.peek().e]++;
            left.poll();
        }
        for (int i = 0; i < N; i++) {
            answer.append(count[i]).append(" ");
        }
    }

    private static boolean union(int s, int e) {
        s = find(s);
        e = find(e);

        if(s == e)
            return false;
        else if(s < e)
            roots[e] = s;
        else
            roots[s] = e;
        return true;
    }

    private static int find(int s) {
        if(roots[s] == s)
            return s;
        return roots[s] = find(roots[s]);
    }


    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer.toString());
        bw.flush();
    }
}

class Edge {
    int s, e;

    public Edge(int s, int e) {
        this.s = s;
        this.e = e;
    }
}