3 7 7 위상 정렬 (Topological Sort)

🚀 **이 문서는 보다 쉽게 이해할 수 있도록 정리되었습니다.**

input : 정점, 간선 정보

TC
5 7
1 2
1 4
1 3
2 5
3 4
4 2
4 5

output
1 3 4 2 5

“`
public class Topology_Sort {

static final int MAX = 101;

static int[] visited = new int [MAX];
static int[] inputEdgeCount = new int[MAX];
static ArrayList ordered = new ArrayList<>();
static ArrayList[] adj = new ArrayList[MAX];

public static void main(String[] args) throws IOException {
for(int i = 0; i();
}

BufferedReader br = new BufferedReader(new InputStreamReader(System.int));
StirngTokenizer st = new StringTokenizer(br.readLine());

int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

for(int i = 0; i< M; i++){ st = new StringTokenizer(br.readLine()); int s = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken()); adj[s].add(e); inputEdgeCount[e]++; } ArrayList result = topologicalSort(N);

for(int i = 0 ; i topologicalSort(int N){
ArrayList startNode = new ArrayList<>();
ordered.clear();
Arrays.fill(visited, 0);

for(int i = 1; i<=N; i++){ if(inputEdgeCount[i] == 0){ startNode.add(i); } } for(int i : startNode){ if(visited[i] == 0) dfs(i); } Collections.reverse(ordered); return ordered; } static void dfs(int u){ visited[u] = 1; for(int v : adj[u]){ if(visited[v] == 0) dfs(v); } ordered.add(u); } } ``` 개발자, 기술사, 삼성, 외국계 IT기업 20년차 기술노트 알렉이 직접 작성한

IT기업 기술 면접을 위한 CS + 면접 노하우 PDF
[https://kmong.com/self-marketing/539751/LUA54VnQsP](https://kmong.com/self-marketing/539751/LUA54VnQsP)
자주 나오는 CS 질문과 답변 그리고 100번 이상 면접관으로 참여하면서 느꼈던

면접자가 알아야 할 팁 13가지 포함

백엔드 개발자를 위한 클라우드 강의, AWS

[https://inf.run/o1NX](https://inf.run/o1NX)

이제는 비전공자도, 일반이도 개발할 수 있다.
ChatGPT를 이용한 누구나 앱개발 with 알렉
[https://inf.run/rpX4](https://inf.ru