그래프6 [백준 4485] 녹색 옷 입은 애가 젤다지? www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net bfs로 풀어도 되지만 다익스트라를 사용해서 풀었다. 다익스트라 사용시 우선순위 큐를 사용함. 다익스트라 구현방법 외우자..ㅠ #include #include #define INF 1e9 using namespace std; int n; int cave[125][125]; int dis[125][125]; struct s { int row, col, cost; }; struct cmp { bo.. 2021. 1. 5. [백준 14588] Line Friends (Small) www.acmicpc.net/problem/14588 14588번: Line Friends (Small) Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다. www.acmicpc.net #include #include #include #define MAX 1e9 using namespace std; struct s { int left, right; }; int n, l, r, q, a, b; s arr[301]; int dis[301][301]; bool check(int a, int b) { if (arr[a].right < arr[b].left || arr[b].right < arr[a].left) { return 0; } retur.. 2021. 1. 2. [백준 5567] 결혼식 www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 트리를 레벨별로 순회하는 문제로 생각하면 된다. root =1 로 잡고 레벨 2가 되는 지점까지 연결된 노드수를 구한다. 1. 입력시 양방향 그래프 구현을 위해 벡터를 사용한다. 2. 루트노드인 1을 큐에 넣고 순회를 시작한다. 3. 레벨별 순회이므로 큐 사이즈만큼 순회한다. #include #include #include using namespace std; int n, m; vector v[501]; boo.. 2020. 12. 29. [백준 9466] 텀 프로젝트 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net directed graph에서 cycle detection 응용문제이다. 사이클에 해당하지 않는 노드를 찾는 문제로 dfs를 사용하거나 indegree + 위상정렬을 사용한다. 1. dfs를 사용할 때 사이클이 있는지 확인할 때 지나간지 여부를 체크하는 배열 path와 확인이 끝났다는 표식인 done 배열 두 가지를 사용한다. 1부터 n까지 done이 아니라면 dfs에 들어가는데 dfs에 들어가서 방문 체크path를.. 2020. 12. 3. 이전 1 2 다음
