Graph cycle 검출 질문 [문제: Dictionary]

  • lee890211
    lee890211

    *정답처리된 답안과 오답처리된 답안의 제 코드 첨부합니다.

    오답 처리된 답안은 그래프 생성중에 그래프 사이클 여부를 검증하는 것이고, 정답 처리된 답안은 그래프 생성이 완료된 후 사이클 여부를 검증합니다.

    오답에서 사이클 여부 검증하는 부분은 만약 Edge A->B를 추가 해야 한다면 B로부터 A까지 도달 할 수 있는지 체크합니다.(만약 가능 할 경우 Edge A->B를 추가 하게되면 사이클이 생기게 되기때문에)

    제가 봤을땐 알고리즘에 문제가 있는지 잘 모르겠는데, 어떠한 상황에 이 알고리즘이 틀리게 되는지 궁굼합니다.

    *사이클 검출로직만 바꿧는데 정답처리되어 그 부분에 문제가 있다고 가정하였습니다. 그래프순서에 관여하지않는 알파벳 순서도 다르게 프린트하지만 이부분은 상관이없으므로.

    정답 ---------------------

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static Set<Integer>[] adj;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int c = Integer.parseInt(br.readLine());
        for (int i=0; i<c; i++) {
            int n = Integer.parseInt(br.readLine());
            String[] words = new String[n];
            adj = new Set['z'-'a'+1];
            boolean[] visited = new boolean['z'-'a'+1];
            for (int j=0; j<n; j++) words[j] = br.readLine();
            for (int j=0; j<visited.length; j++) adj[j] = new HashSet<>();
            for (int j=1; j<n; j++) {
                int len = Math.min(words[j-1].length(), words[j].length());
                for (int k=0; k<len; k++) {
                    int prev = words[j-1].charAt(k)-'a';
                    int curr = words[j].charAt(k)-'a';
                    if (prev != curr) {
                        visited[prev] = visited[curr] = true;
                        adj[prev].add(curr);
                        break;
                    }
                }
            }

            System.out.println(dfsAll(visited));
        }
    }
    static String dfs(boolean[] rec, boolean[] visited, int now, StringBuilder builder) {
        visited[now] = true;
        rec[now] = true;
        for (int e : adj[now]) {
            if (rec[e]) return "INVALID HYPOTHESIS";
            if (!visited[e]) {
                String ret = dfs(rec, visited, e, builder);
                if (ret != null) return ret;
            }
        }
        rec[now] = false;
        builder.append((char)('a'+now));
        return null;
    }
    static String dfsAll(boolean[] actual) {
        StringBuilder builder = new StringBuilder();
        boolean[] canVisit = new boolean['z' - 'a' + 1];
        boolean[] rec = new boolean['z' - 'a' + 1];
        for (int i=0; i<adj.length; i++) {
            if (actual[i] && !canVisit[i]) {
                canVisit[i] = true;
                String ret = dfs(rec, canVisit, i, builder);
                if (ret != null)
                    return ret;
            }
        }
        for (int i=0; i<adj.length; i++) {
            if (!canVisit[i]) {
                canVisit[i] = true;
                dfs(rec, canVisit, i, builder);
            }
        }
        builder.reverse();
        return builder.toString();
    }
}

    오답 --------------

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static List<Integer>[] adj;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int c = Integer.parseInt(br.readLine());
        for (int i=0; i<c; i++) {
            int n = Integer.parseInt(br.readLine());
            String[] words = new String[n];
            adj = new List['z'-'a'+1];
            boolean[] visited = new boolean['z'-'a'+1];
            boolean ret = true;
            for (int j=0; j<n; j++) words[j] = br.readLine();
            for (int j=0; j<visited.length; j++) adj[j] = new ArrayList<>();
            for (int j=1; j<n; j++) {
                int len = Math.min(words[j-1].length(), words[j].length());
                for (int k=0; k<len; k++) {
                    int prev = words[j-1].charAt(k)-'a';
                    int curr = words[j].charAt(k)-'a';
                    if (prev == curr) continue;
                    if (visited[prev] && visited[curr]) {
                        boolean[] canVisit = new boolean['z'-'a'+1];
                        dfs(canVisit, curr);
                        if (canVisit[prev]) {
                            ret = false;
                            break;
                        }
                        adj[prev].add(curr);
                    } else {
                        visited[prev] = visited[curr] = true;
                        adj[prev].add(curr);
                    }
                    break;
                }
                if (!ret) break;
            }

            if (!ret)
                System.out.println("INVALID HYPOTHESIS");
            else {
                boolean[] canVisit = new boolean['z' - 'a' + 1];
                System.out.println(dfsAll(visited, canVisit));
            }
        }
    }
    static StringBuilder dfs(boolean[] visited, int now) {
        visited[now] = true;
        StringBuilder builder = new StringBuilder();
        builder.append((char)('a'+now));
        for (int e : adj[now]) {
            if (!visited[e]) {
                builder.append(dfs(visited, e));
            }
        }
        return builder;
    }
    static String dfsAll(boolean[] actual, boolean[] visited) {
        StringBuilder builder = new StringBuilder();
        for (int i=0; i<adj.length; i++) {
            if (actual[i] && !visited[i]) {
                visited[i] = true;
                builder.insert(0, dfs(visited, i));
            }
        }
        for (int i=0; i<adj.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                builder.append(dfs(visited, i));
            }
        }
        return builder.toString();
    }
}

    8년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.