본문 바로가기

vividswan

Notice

블로그 이전 완료

Recent Posts

Popular Posts

Recent Comments

Link

깃허브

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

위상정렬

Algorithm/BOJ 2022. 3. 5. [BOJ] 줄 세우기(2252) [백준(BOJ)] ACM Craft(2252) C++ 문제 : BOJ_2252번 줄 세우기 문제 설명 위상정렬, bfs 위상정렬을 이용해서 순서를 출력하는 기본적인 문제입니다. N 명의 학생 중 서로 줄을 세운 M 개의 경우의 순서만 고려하고 줄을 세운 관계가 아니라면 아무 순서나 상관없이 출력할 수 있습니다. Solution 순서대로 배열하기 위해 indegree를 이용한 위상정렬을 해줘야 하므로, indegree라는 배열을 만들어 순서를 벡터에 연결해줄 때마다 배열의 수를 올려주며, 큐에 집어넣을 때는 들어오는 모든 간선을 탐색한 경우에만 push 해주는 방식으로 소스를 짜야 합니다. #include #include #include using namespace std; int stu, rel, ind..

Algorithm/BOJ 2022. 3. 5. [BOJ] ACM Craft(1005) [백준(BOJ)] ACM Craft(1005) C++ 문제 : BOJ_1005번 이모티콘 문제 설명 위상정렬, dp, bfs 각 건물마다 그 건물을 짓기 위해서 먼저 지어져야 하는 건물들이 존재하고, 먼저 지어야 하는 건물이 없는 건물부터 시작하여 지정된 거물을 지을 때까지 걸리는 최소 시간을 작성하는 문제입니다. 건물에 대한 앞뒤 관계가 있고, 사이클이 아니기 때문에 indegree를 이용한 위상정렬 문제입니다. 그리고 먼저 지어야 하는 모든 건물이 지어져야 다음 건물이 지어지므로, dp를 활용하여 건물이 지어질 수 있는 최소 시간을 구할 수 있습니다. Solution 한 건물이 지어지는 시간을 모두 입력받고(wait[]), 최종적으로 그 건물이 지어질 수 있는 최소 시간에 대한 배열을 만든 뒤(res..

Algorithm/BOJ 2022. 3. 5. [BOJ] 새끼치기(17291) [백준(BOJ)] 새끼치기(17291) C++ 문제 : BOJ_17291번 새끼치기 문제 설명 위상정렬, DP(다이나믹 프로그래밍) 1년에 한 마리였던 벌레가 매년 분열하고 1)홀수 연도에 분열했던 벌레는 3번 분열 시 사망 2)짝수 연도에 분열했던 벌레는 4번 분열시 사망 임으로, 해당 년도에 살아있는 벌레들이 언제 분열했는지를 저장해야 됨으로 2중 dp를 통해 풀 수 있습니다. Solution 이중 배열을 dp[현재 연도][태어난 연도] = 벌레 수 로 정해서 풀어봅시다. 2중 포문을 통해 매년마다 dp[현재 연도][현재 연도] = dp[현재 연도-1][태어난 연도] 로 분열된 벌레를 저장해준다. 기존에 남아있던 벌레는 홀수 3년, 짝수 4년 안에 분열된 벌레라면 dp[현재 연도][분열된 연도] = ..

Algorithm/BOJ 2022. 3. 5. [BOJ] 양 구출 작전(16437) [백준(BOJ)] 양 구출 작전(16437) C++ 문제 : BOJ_16437번 양 구출 작전 문제 설명 위상정렬, bfs 제목만 귀엽고 문제는 징그러운 양 구출 작전입니다. 문제에 정확히 제시되어 있는 '1번 섬으로 가는 경로는 유일' 을 주의해서 읽어야 하고, 각 섬에 양 혹은 늑대가 있는 데, 섬에 양이 있다면 다음 섬으로 넘어가는 양의 수가 누적되고, 늑대가 있다면 늑대의 수만큼 양의 수가 줄어들고, 양을 한 마리 잡아먹은 늑대는 더 이상 양을 잡아먹지 않기 때문에 늑대의 수도 줄은 것과 같습니다. 문제에서 친절하게 그림을 제시해주었는데, (두 번째 테스트 케이스에 대한 그림) n 번 째 섬과 연결된 섬들의 모든 양이 누적되어 n 번 째 섬에 도착하는 방식입니다. 즉, 양의 누적수를 파악하기 위해..

이전 1 다음

티스토리툴바