René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"[Week 6] DICTIONARY self review - Yunhyunjo","articleBody":"# DICTIONARY self review ![](https://img.shields.io/badge/-WA-%23e00000)\r\n\r\n## 1. 해결 시도 과정\r\n위상정렬을 위해 indegree와 ch를 선언하여 저장하고 인접리스트를 만들어 정렬을 시도하였습니다.\r\n\r\n## 2. 작성한 코드와 설명\r\n```cpp\r\nwhile (c--) {\r\n\t\tstring s, p;\r\n\t\tfill(indegree.begin(), indegree.end(), 0);\r\n\t\tfill(ch.begin(), ch.end(), 0);\r\n\t\tvector \u003cvector \u003cint\u003e\u003e v(26);\r\n\t\tcin \u003e\u003e n \u003e\u003e s;\r\n\t\tp = s;\r\n\t\tch[p[0] - 97] = 1;\r\n\t\tfor (int i = 1; i \u003c n; i++) {\r\n\t\t\tcin \u003e\u003e s;\r\n\t\t\tif (p[0] != s[0]) {\r\n\t\t\t\tif (ch[s[0] - 97] == 0) ch[s[0] - 97] = 1;\r\n\t\t\t\tindegree[s[0] - 97]++;\r\n\t\t\t\tv[p[0] - 97].push_back(s[0] - 97);\r\n\t\t\t}\r\n\t\t\telse {\r\n\t\t\t\tint pp = 1;\r\n\t\t\t\twhile (pp \u003c p.size() \u0026\u0026 pp \u003c s.size()) {\r\n\t\t\t\t\tif (p[pp] != s[pp]) {\r\n\t\t\t\t\t\tif (ch[p[pp] - 97] == 0) ch[p[pp] - 97] = 1;\r\n\t\t\t\t\t\tif (ch[s[pp] - 97] == 0) ch[s[pp] - 97] = 1;\r\n\t\t\t\t\t\tindegree[s[pp] - 97]++;\r\n\t\t\t\t\t\tv[p[pp] - 97].push_back(s[pp] - 97);\r\n\t\t\t\t\t\tbreak;\r\n\t\t\t\t\t}\r\n\t\t\t\t\tpp++;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\tp = s;\r\n\t\t}\r\n\t\tcout \u003c\u003c topologySort(v) \u003c\u003c endl;\r\n\t}\r\n```\r\n먼저 입력된 순서대로 비교하여 인접리스트를 만들고 indegree도 구해주었습니다. \r\n두 단어의 0번째 값이 같을 경우에는 다음 인덱스의 해당하는 문자를 비교해주었습니다. \r\n그렇게 구한 인접리스트를 topologySort함수에 매개변수로 넘겨주어 위상정렬을 해 출력해 주었습니다.\r\n\r\n```cpp\r\nstring topologySort(vector \u003cvector \u003cint\u003e\u003e\u0026 v) {\r\n\tstring s = \"\";\r\n\tqueue \u003cint\u003e q;\r\n\tfor (int i = 0; i \u003c 26; i++) {\r\n\t\tif (ch[i] == 1 \u0026\u0026 indegree[i] == 0) {\r\n\t\t\tq.push(i);\r\n\t\t}\r\n\t}\r\n\r\n\twhile (!q.empty()) {\r\n\t\tint x = q.front();\r\n\t\tq.pop();\r\n\t\tchar c = x + 97;\r\n\t\ts += c;\r\n\t\tfor (int j = 0; j \u003c v[x].size(); j++) {\r\n\t\t\tif (v[x][0] == 50) return \"INVALID HYPOTHESIS\";\r\n\t\t\tif (--indegree[v[x][j]] == 0) q.push(v[x][j]);\r\n\t\t}\r\n\t\tv[x].clear();\r\n\t\tv[x].push_back(50);\r\n\t}\r\n\tif(s == \"\") return \"INVALID HYPOTHESIS\";\r\n\tfor (int i = 0; i \u003c 26; i++) {\r\n\t\tif (ch[i] == 0) {\r\n\t\t\tchar c = i + 97;\r\n\t\t\ts += c;\r\n\t\t}\r\n\t}\r\n\treturn s;\r\n}\r\n```\r\nqueue를 사용하여 일단 indegree값이 0인 값을 넣어주었습니다. 그 다음 bfs를 통해 위상정렬을 해 주었습니다.\r\n순환을 막기위해 이미 정렬에 사용한 정점 리스트는 clear해준 다음 값 50을 넣어주었고, for 문을 돌때 0번째 값이 50이면 이미 정렬에 사용한 정점으로 순환된 것 이므로 바로  INVALID HYPOTHESIS를 리턴해주었습니다.\r\n또 indegree가 0인 것이 없어 s가 비어있을 경우에도 순환이란 뜻이므로 INVALID HYPOTHESIS를 리턴해주었습니다.\r\n\r\n## 3. 막힌 점 및 개선 사항\r\n예제 입력은 정답이 제대로 나와서 정확히 어디서 틀린지를 모르겠습니다. 만약 똑같은 순서가 중복으로 나올 때 어차피 topologySort함수에서 걸러지므로 인접리스트 만들때 처리를 안해줬는데 처리하는 코드를 넣어줘야할 것 같습니다.","author":{"url":"https://github.com/Yunhyunjo","@type":"Person","name":"Yunhyunjo"},"datePublished":"2022-03-03T13:08:35.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/184/Advanced-Algorithm-Study/issues/184"}