코딩/알고리즘 (67) 썸네일형 리스트형 백준 11657 타임머신 벨만포드 알고리즘을 수행하면서, 음수사이클이 있을 경우 -1 출력 참고 : 벨만포드 알고리즘 http://deque.tistory.com/72백준 1865 웜홀 http://deque.tistory.com/71 //deque.tistory.com #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include using namespace std; template class triple { public: FIRST first; SECOND second; THIRD third; triple(FIRST a, SECOND b, THIRD c) { first = a; secon.. 백준 1865 웜홀 밸만포드 알고리즘을 시행하고 음수사이클이 있으면 YES를 출력하면 된다. triple이란 클래스를 하나 만들어봤다. 그래프 알고리즘 풀때마다 매번 이것저것 하는것도 귀찮아서 pair처럼 하나 만들었다. //deque.tistory.com #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include using namespace std; template class triple { public: FIRST first; SECOND second; THIRD third; triple(FIRST a, SECOND b, THIRD c) { first = a; second = b.. 백준 1504 특정한 최단 경로 꼭 거쳐야 하는 노드가 각각 mustVertex1, mustVertex2 라고 하자. 그렇다면 노드1 -> mustVertex1 -> mustVertex2 -> 노드N노드1 -> mustVertex2 -> mustVertex1 -> 노드N 의 경로 중 짧은 것이 정답이 된다. 각 경로는 다음과 같이 다익스트라 알고리즘을 세번 수행하면 결과를 얻을 수 있다. 1. 노드1에서 시작하는 다익스트라 이것으로 1 ->mustVertex1, 1 -> mustVertex2을 얻을 수 있다. 2. 노드N에서 시작하는 다익스트라 N -> mustVertex1, N -> mustVertex2 를 얻을 수 있다. 3. mustVertex1에서 시작하는 다익스트라 mustVertex1 -> mustVertex2를 얻을 수 있.. 백준 1753 최단경로 간단하게 다익스트라 알고리즘을 이용하면 해결되는 문제.시간이 짧기 때문에 우선순위 큐를 써야 하고, 우선순위 큐의 기본 정렬은 내림차순이기때문에 오름차순으로 변경하기 위해priority_queue pq;로 우선순위 큐를 선언했다. 헤더에 functional을 꼭 넣어야 한다. 그리고 printf()를 안쓰고 깜빡하고 cout을 썼는데 이거 때문에 시간초과 나버렸다. 아깝 //deque.tistory.com #define _CRT_SECURE_NO_WARNINGS #define INT_MAX_ 2100000000 #include #include #include #include #include #include #include #include using namespace std; int V, E, K; vec.. 백준 1766 문제집 A, B가 들어오면A->B 의 edge를 만들고완성된 그래프에 대해 위상정렬을 수행하는 문제. 단 위상정렬을 할 때 위상정렬큐에 indegree(진입차수)가 0인 노드를 한번에 다 넣지 말고 한번에 하나씩만 넣어야 한다. 풀이하자면 다음과 같다 #indegree가 0인 노드를 하나만 찾아서 그것 하나만 큐에 넣는다(다른 것과 다르게 모두 넣지 않는다.).큐에서 하나를 빼고 그 노드의 진입차수를 1뺀다(-1로 만들어주어 다음 계산시에 영향을 끼치지 않게 한다.).그 노드와 연관된 vertex들의 indegree를 1 뺀다.다시 루프 처음으로 돌아간다.# 이런 식으로 하면 큐에 가장 적은 숫자부터 들어가니 낮은 번호부터 나오게 되어 문제의 조건3을 만족한다. 그런데 이 알고리즘대로 수행하면 큐가 필요 없다... 백준 1516 게임 개발 A를 짓고 B를 지어야 한다면A->B와 같이 모델링 한 뒤,위상정렬을 수행하면서 시간을 계산한다. 여기서 defaultTime은 기본 건설 시간,addTime은 건설을 위해 선행으로 지어야 하는 건물들을 건설하기 위해 기다리는 시간이다. 그래프가 다음과 같다고 하자 A->EF->CB->C->D->E 이럴 경우 E를 짓는 시간은E를 짓는 기본 시간(defaultTime[E])+E의 선행 건물들의 건설 시간중 최대값(addTime[E])이다. addTime[E]는 A의 총 건설 시간과 D의 총 건설시간의 최대값이고, A의 총 건설 시간은 defaultTime[A]이다.한편 D의 총 건설 시간은 C의 총 건설 시간 + D의 기본 건설시간이고,이때 C의 총 건설 시간은 위상정렬을 하면서 C에 접근했을때 (def.. 백준 2252 줄세우기 M번 들어오는 학생의 쌍이 다음과 같이 들어온다고 가정하자. (3, 2)(4, 1) 그렇다면, 3은 2보다 앞에 , 4는 1보다 앞에 있어야 한다는 뜻이다.이를 다음과 같은 그래프로 모델링 하자 3->24->1 그 후 이 그래프에 대해 위상정렬을 수행하면 적절한 정답이 도출된다. 한편, 정답이 여러개인 경우 하나만 출력하라고 하였다.이것은 edge가 없는 vertex에 대해 고려를 하지 않아도 되는 장점을 부여한다. 이를테면, 위와 같은 예가 있는데, 사실 학생의 수가 4명이 아니고 10명쯤 된다고 하자. 그렇다면 5번부터 10번까지의 학생은 indegree를 0으로 두고,indegree순으로 위상정렬을 수행할때 5번부터 10번까지의 학생의 indegree는 0이기 때문에 먼저 출력된다.edge가 없는 .. 백준 3665 최종순위 풀이는 다음과 같다. 팀을 vertex, 팀의 우열관계를 edge로 하여 방향그래프를 만든다. 이때 주의할 점은 가능한 모든 edge를 다 넣는 것이다. 예를 들어, 4 3 2 1이 주어졌다고 하자(팀4가 1등, 팀1이 4등)그렇다면 방향그래프는 4 -> 34 -> 24 -> 1 3 -> 23 -> 1 2 -> 1 와 같이 6개의 edge로 구성되어 있어야 한다. 그 후 팀의 우선순위가 바뀌는 쌍을 입력받는다.이 쌍은 방향이 바뀌는 edge의 노드 쌍이다. 예를 들어, 위와 같은 그래프일때 (4, 1)(3, 2) 를 입력받았다면 4 -> 34 -> 24 1 와 같은 그래프로 바뀐다 그 후, 이 그래프를 위상정렬을 하여 팀의 등수를 나타내는 것이 이 문제의 풀이이다. From노드로부터 To노드로 연결되어 .. 이전 1 2 3 4 5 6 7 ··· 9 다음