dictionary 문제 질문

  • zzerross
    zzerross

    책의 풀이는 참고만 하고, STL없이 풀고 있는데요.

    cycle 처리랑 random data도 꽤 생성해서 검수해봤는데, 몇일째 오답이네요.

    문제를 먼가 잘못 해석하고 있는거 같은데, 도통..모르겠네요.

    DICTIONARY

    소스코드

    /**
 * @ref https://algospot.com/judge/problem/read/DICTIONARY
 * @since 2014.08.11
 */

#include <stdio.h>

// #define debug

#ifdef debug
#define pr printf
#else
#define pr
#endif

struct dc {
    static const int sz = 1000;
    static const int ln = 21;
    static const int na = 'z' - 'a' + 1;

    char buf[sz][ln];
    int nr;

    int gm[na][na];
    int gv[na];
    int go[na];
    int gi[na];

    struct q {
        int b[na];
        int f, r;
    } q;

    int ti(char c) { return c - 'a'; }
    char tc(int i) { return 'a' + i; }

    void read() {
        scanf("%d", &nr);

        for (int i = 0; i < nr; i++)
            scanf("%s", buf[i]);

        for (int v = 0; v < na; v++)
            go[v] = gi[v] = gv[v] = 0;

        q.f = q.r = 0;
    }

    void make() {
        for (int v = 0; v < na; v++)
            for (int e = 0; e < na; e++)
                gm[v][e] = 0;

        for (int i = 1; i < nr; i++) {
            for (char *a = buf[i-1], *b = buf[i]; *a && *b; a++, b++) {
                if (*a != *b) {
                    if (!gm[ti(*a)][ti(*b)]) {
                        gm[ti(*a)][ti(*b)] = 1;
                        go[ti(*a)]++;
                        gi[ti(*b)]++;
                    }
                    break;
                }
            }
        }

        dump();
    }

    int dfs(int v) {
        if (gv[v]++ > 0) return 0;

        for (int e = 0; e < na; e++)
            if (gm[v][e])
                if (!dfs(e))
                    return 0;

        return (q.b[q.r++] = v) || 1;
    }

    int dfs() {
        for (int v = na - 1; v >= 0; v--)
            if (!go[v] && !gi[v])
                dfs(v);

        for (int v = 0; v < na; v++)
            if (go[v] && !gi[v])
                if (!dfs(v))
                    return q.r = 0;

        return q.r;
    }

    void out() {
        if (q.r == na) {
            for (int c; q.r--;) {
                printf("%c", tc(c = q.b[q.r]));
                gv[c] = 1;
            }
        } else {
            printf("INVALID HYPOTHESIS");
        }

        printf("\n");
    }

    void dump() {
#ifdef debug
        printf("         ");

        for (int v = 0; v < na; v++)
            printf("%c ", tc(v));

        printf("\n");

        for (int v = 0; v < na; v++) {
            printf("%2d %2d %c: ", go[v], gi[v], tc(v));

            for (int e = 0; e < na; e++)
                printf("%d ", gm[v][e]);

            printf("\n");
        }
#endif
    }
};

struct dc d;

#if 1
int main() {
    int tc;

    for (scanf("%d", &tc); tc-- > 0;) {
        d.read();

        d.make();

        d.dfs();

        d.out();
    }
    return 0;
}
#else
#include <stdlib.h>
int main() {
    int tc = rand() % 50 + 1;

    printf("%d\n", tc);

    for (int t = 0; t < tc; t++) {
        int ns = rand() % 1000 + 1;

        printf("%d\n", ns);

        for (int i = 0; i < ns; i++) {
            int nc = rand() % 20 + 1;

            for (int j = 0; j < nc; j++) {
                printf("%c", 'a' + rand() % 26);
            }
            printf("\n");
        }
    }
    return 0;
}
#endif

    "만약 가능한 순서가 여러 개 있다면 아무 것이나 출력해도 좋습니다."
    를 먼가 잘못 해석하고 있는지 싶기도 하구요.

    혹시나,

    • 하나인 경우

    1
    1
    z

    답이 아래여도 맞는 것이겠지요?

    abcd ~ xyz

    • 순서

    dictionary
    english
    is
    ordered
    ordinary
    this

    책과는 다르게 아래와 같이 출력해도 맞지 않나요?
    deiotabcd~xyz


    9년 전
11개의 댓글이 있습니다.
  • Being
    Being

    dfs(int v) 에서 v가 0이면 거짓으로 간주되지 않을까요?


    9년 전 link
  • zzerross
    zzerross

    새벽내 테스트 해보고...아직도...삽질 중이네요..ㅋ
    조언 정말 감사합니다..

    일단..
    dfs(int v)에서는
    . 두번 vertex가 방문되면 0 반환으로 cycle 발생함을 알리거나
    . 그렇지 않은 경우는 1을 반환하도록 하였습니다

    조언해 주신 dfs(v=0) 즉 a의 경우도 다시 확인해 봤는데 정상인거 같습니다.
    1
    1
    b
    a

    bacde~z
    로 나오거든요


    9년 전 link
  • zzerross
    zzerross

    혹시나..gv[v]=0인 경우를 말씀하신 거면..
    ++가 후치연산이라 조건문은 false로 넘어가서..
    return 0 되지 않소 있구요

    if (gv[v]++ > 0) return 0;

    시나


    9년 전 link
  • Kureyo
    Kureyo

    1
    3
    itct
    iyc
    ytji
    가 INVALID 뜨시는데 이거 답 되지않나요ㅜㅜ?


    9년 전 link
  • zzerross
    zzerross

    저도 오늘 틈틈히 random data 생성해서 검토해보니,
    아래와 같은 case가 문제더라구요.
    Kureyo 님, 조언해주신 것 같은 case에 오답이어서, 재수정했네요.
    그래도 역시나, 오답...잘못 구현된 case가 더 있나바요..쩝...

    2
    8
    b
    bo
    bk
    od
    oj
    oo
    oan
    oal
    8
    b
    bo
    bk
    od
    oj
    oo
    jan
    jal


    9년 전 link
  • zzerross
    zzerross

    결국,
    dfs()에서 cycle도 같이 검사하도록 해보자는 욕심이 삽질을 부르게 되었었네요.
    아무리 머리를 싸메도 깔끔한 방법이 없어,
    책에서 처럼 cycle 검사를..ㅜ.ㅡ 해서 정답처리됐네요.

    혹시 dfs() 내에서 cycle 검사하는 방법 아시는 분 있을까요?
    그리고, 이런 글은 spoiler 성이 있으면, 삭제 하는게 좋을까요?


    9년 전 link
  • VOCList
    VOCList

    dfs는 사이클을 찾기 위해 많이 쓰이는 방법 중 하나입니다.
    https://www.google.com/search?q=dfs%20cycle&gws_rd=ssl

    많은 분들이 질문글에 답변을 받고 난 뒤에 삭제하곤 하시는데 개인적으로 좋아보이진 않네요. 나중에 해당 문제에 대해서 궁금한 사람이 검색을 해 볼 수도 있는거고 공들여 답변을 작성해주신 분들 입장에서는 난데없이 작성했던 글이 날아가게 되니까요.


    9년 전 link
  • zzerross
    zzerross

    @VOCList 님, 답변 감사합니다. ^^

    제가 "dfs() 내에서 cycle 검사하는 방법"을 질문해 본 것은,
    dictionary 문제에서 사전 순서를 만들기 위해,
    dfs(int v)를 수행하는 과정내에서 임의의 v를 방문했을 때,

    • cycle인지? (ex, a->c->b)
    • 중복 방문인지? (ex, a->c, b->c) 를 동시에 확인하는 방법이었습니다.

    종만님의 책의 코드를 보면서,
    굳이 dfs() 종료 후에 별도의 loop를 돌면서,
    역방향 edge를 검사해야 할까?
    라는 의문이 있었거든요.


    9년 전 link
  • JongMan
    JongMan

    제 생각엔 그게 더 이해하기 쉬워서 그렇게 했습니다. ^^; 물론 dfs 하시면서 체크해도 될거에요~


    9년 전 link
  • zzerross
    zzerross

    @JongMan님, 답변 감사합니다. ^^
    dfs() 내에서 check하는 걸 약간 포기했었는데, 다시 도전해봐야 겠네요..ㅋ


    9년 전 link
  • nberserk
    nberserk

    @zzerross 저는 사이클과 traverse를 dfs에서 해결했어요.
    여기 코드 참고하시면 도움이 될것 같습니다.
    https://github.com/nberserk/codejam/blob/master/cpp/codejam/dictionary.cpp


    9년 전 link

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