[BOJ] 백준 2848번 : 알고스팟어

date

May 26, 2023

slug

boj-2848

author

status

Public

category

🧩 Problem Solving

tags

BOJ

summary

큐를 사용하여 위상정렬을 구현해보자!

type

Post

thumbnail

문제링크

2848번: 알고스팟어

https://www.acmicpc.net/problem/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