🧩 Problem Solving
[BOJ] 백준 2848번 : 알고스팟어
문제링크
아이디어
1. 간선 생성 및 차수
- 각 단어마다 이전 단어와 비교하여 달라지는 부분에서의 알파벳 순서를 간선으로 생성
- ex)
- 이전 단어 : abcd
- 현재 단어 : abce
- ⇒ d→e 간선
- 간선 추가
- boolean[][]
- 27*27 의 메모리 필요, 불필요한 메모리를 차지하므로 채택X
- List<>[]
- 중복된 간선을 체킹하기 어려움(매번 모든 간선을 조회해야 함)
- HashSet<>[]
- 중복된 간선을 제외하면서 필요한 메모리만 사용할 수 있으므로 채택O
- HashSet → List 변환 : List<> list = new ArrayList<>(hashSet);
2. 위상정렬(큐 사용)
- indegree = 0 인 노드를 큐에 추가
- 큐가 빌 땔까지
- 큐에서 poll 한 후 해당 노드에서 뻗어나가는 간선의 도착노드들의 indegree -= 1;
- 해당 도착노드들의 indegree==0이 되면 큐에 넣기
- 아직 indegree≠0인 노드가 남아있다면 이는 즉 사이클이 존재한다는 의미 ⇒ 위상정렬 불가능
반례
! 와 ? 사이의 우선순위 관련
만약, 올바른 순서가 없다면 "!"를, 가능한 순서가 두 개 이상이라면 "?"를 출력한다.
예를 들어,
4 gx tx hx tf // indegree g x t h f 0 0 2 1 0
인 경우 t→h, h→t 의 사이클을 형성하여 ! 를 출력해야 하는데
queue 에 indegree=0인 알파벳이 2개 이상이 들어오기 때문에 ?를 출력하게 됨
? 는 가능한 순서가 있음이 전재되어야 하므로
사이클을 형성하는 경우 가능한 순서가 없기 때문에 무조건 !을 출력해야 한다