2023년 9월 2일 알고리즘 문제풀이 문제 1 백준 1948 문제 링크 1차 시도 나의 생각 위상정렬을 이용해 풀고자 하였다. 단 시작지점은 진입차수가 0인 것이 문제의 조건이므로 큐에 시작도시를 넣고 반복하였다. 결국 도착지에 갈때까지 비용을 계속 더해주고, 간선을 이용할 떄마다 카운트 해주었다. 예제를 입력했을 떄 결과값이 실제 정답보다 크게 나오기도 했고, 경로 탐색이 내가 예상한대로 되지 않았다. 아무래도 문제를 제대로 이해하지 못한채 그냥 위상정렬만 적용해서 해결하지 못하고 있는것 같다. 애초에 이 문제를 왜 위상정렬로 풀어야 하는지도 모르겠다.. 공부해봐야겠다. ...
2023년 9월 1일 알고리즘 문제풀이 문제 1 백준 2252 문제 링크 1차 시도 위상정렬에 대한 개념을 다 까먹어서 어떻게 풀지 감이 안왔다.. 해서 위상정렬을 공부해보고 풀었다. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 순서가 정해져있는 작업을 차례대로 수행할 때 순서를 결정하는 방법이다. 이번 문제도 어떤 학생들은 순서에 맞게 배열해야 하니 위상 정렬 문제로 풀 수있다. 위상 정렬의 과정은 다음과 같다. 방향이 있는 간선들의 정보가 주어지면 인접그래프를 만든다. 정점의 번호를 index로 하는 배열을 만든 후 해당 정점이 도착지가 되는 간선이 있을 떄마다 정점의 값을 1 올린다. 이 정점의 값이 진입차수를 의미한다. 해당 정점으로 진입하는 간선이 몇개인지를 나타내는 것이다. 위 과정이 완료되면 값이 0인 정점은 큐에 삽입한다. 큐에서 한 정점씩 꺼내어 해당 정점과 연결된 간선을 모두 제거한다. 이 과정에서 값이 0이 된 정점은 큐에 삽입하고 과정을 반복한다. 큐에서 꺼내지는 순서가 작업의 순서이다. 이 문제에 대입해보면, 문제의 입력값에서 순서가 있는 학생이 주어진다. 학생을 정점이라 생각하고 배열의 선후관계를 간선의 방향이라고 생각하면 된다. 코드는 다음과 같다. ...