위상 정렬2 [자바] 백준 14567 - 선수과목 (Prerequisite) (java) 목차 문제 : boj14567 필요 알고리즘 위상 정렬 위상 정렬을 응용해서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 위상 정렬을 응용해서 해결했다. 아래와 같이 해당 정점에서 선수과목이 몇 개 인지 따로 기록해둔다. 이걸 차수라고 하겠다. 선수 과목이 없는 과목부터 몇 학기에 이수했는지(거리) 알기 위해 bfs를 돌린다. 이 때 큐에 넣을 시 차수를 1씩 빼고, 해당 정점의 차수가 0이 되면 큐에 넣는다.. 2023. 11. 26. 백준 2252 자바 - 줄 세우기 (BOJ 2252 JAVA) 문제 : boj2252 1. 그래프로 생각해보자. 이런식으로 A에서 B로 향한다던지, A와 B가 연관되었다든지 하면 일단 그래프로 생각해보는게 이해하기 편하다. 이 문제에서는 'A가 학생 B의 앞에 서야 한다'에 대해 A에서 B로의 간선을 긋는 방향 그래프로 생각해보자. 그럼 다음과 같은 경우를 보자. 5 3 1 2 2 3 4 5 위의 경우를 그래프로 나타내보면 다음과 같다. 위와 같은 경우는 간단하다. 이 문제의 경우 1->2->3을 먼저 가던지, 4->5를 먼저 가던지, 심지어 1->4->2->3->5 이렇게 가던지 상관없다. 서로 섞여있더라도 아무튼 모든 경우에서 A가 B보다 먼저 나오기만 하면 된다. 그렇다면 M개의 A, B를 입력받으면서, A에 나타났으면서 B에는 등장하지 않은 1과 4어디에서든.. 2022. 1. 21. 이전 1 다음
