Algorithm/Topology Sort (4) 썸네일형 리스트형 (C++) - 백준(BOJ) 21276번 : 계보 복원가 호석 https://www.acmicpc.net/problem/21276 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 위상정렬과 정렬을 이용한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. n을 입력받습니다. 인접리스트를 만들어주기 위해서는 index를 int형으로 접근하도록 자료를 정리할 필요가 있습니다. map으로 이를 해결합니다. 나온 이름에 대해 자동으로 key값을 기준 오름차순 정렬을 해주기 때문에 편리합니다. [이름, 이름을 치환한 숫자], 반대로 두 개의 map을 선언합니다. 2. .. (C++) - 백준(BOJ) 14676번 : 영우는 사기꾼? https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 위상정렬 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 일차원 배열 선언 : 건설여부를 저장할 buildCheck 진입차수를 저장할 indegree를 선언합니다. 입력받은 정보를 토대로 단방향 인접리스트 그래프 graph를 생성합니다 그리고 진입차수를 저장합니다. 치트를 썻는지의 여부 bool형 변수 isCheat를 선언합니다. 📔 풀이과정 x를 건설할 경우 x가 .. (C++) - 백준(BOJ) 1005번 : ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상정렬 문제였습니다. 풀이방법 1. 기존 위상정렬 문제처럼 x번을 지을 조건이 되면 바로 지을 수 있는 것이아닌 x번 건물의 선제조건인 건물들 중 건설시간이 가장 오래걸리는 건물이 다 지어져야 해당 건물을 지을 수 있습니다. 2. 적절히 입력을 받습니다. 단 방향 그래프의 형태이며 인접리스트로 저장했습니다. 또한 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다. 의미는 그래프의 형태로.. (C++) - 백준(BOJ) 1516번 : 게임개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬문제였습니다. 풀이방법 짓는데 오래걸리는 순으로 pq에 넣어 꺼내 확인하면서 진입차수를 줄여가는 방식으로 구현합니다. 진입차수가 0이라면 현재정점 x가 가장 최적으로 지을 수 있는 건물이므로 x의 시간을 next정점의 시간에 더해서 갱신해줍니다. Code #include using namespace std; int n, ind[501]; struct Edge {int v, w; .. 이전 1 다음