Jonyo Programming

[BOJ 9470(G3)리뷰] 처음에 문제 설명만 읽고는 문제를 이해하기 힘들었다. 결국은 위상정렬 문제인데 특별한 조건이 추가된 위상정렬이라고 생각하면 된다. 강이 시작하는 노드(들어오는 간선이 없는 경우)의 순서는 1번부터 시작한다. 입력은 "1 3"이런식으로 주어지는데 1번강에서 3번강으로 물이 흘러나간다는 소리이다. 이 때 들어오는 간선이 존재하는(3번노드) 노드의 정보는 자신에게 들어오는 노드 중 가장 큰 값의 크기에 따라 결정된다. 가장 큰 값이 2개 이상일 경우 이전 강의 값에 +1, 2개 미만일 경우는 이전 강의 정보를 그대로 가진다. 위 조건을 만족하기 위하여 별도의 배열을 만들었다. 해당 번호에 들어오는 물 중 가장 큰 값과, 그 갯수를 저장하는 코드를 추가했다. 나머지는 위상정렬 알고..

[BOJ 2252(G2)리뷰] N명의 학생들을 키 순서대로 줄 세우려고한다. 이 때 학생들의 키를 알지 못하여 두 학생의 키를 비교한 결과를 통해 정렬하려고 한다. 예를들어, "1번학생이 3번보다 크고 3번학생이 2번보다 크다" 라고 한다면 이 세 학생의 키 순서는 1>3>2 가 될 것이다. 학생들의 정보가 주어졌을때 학생들의 키 순서대로 출력을 해야 한다. 이 문제는 위상정렬이라는 알고리즘을 통하여 해결할 수 있다. 주어진 정보를 그래프로 구성해보자. 만약 "1번학생이 3번보다 크다"라는 정보가 있다면 (1) > N >> M; for (int i = 0; i > a >> b; adj[a].push_back(b); indegree[b]++; } //inde..