그래프

[프로그래머스 level 3] 네트워크 (C++)

BFS 또는 DFS로 풀 수 있는 문제이다. 위 그래프는 2개로 나눌 수 있다. 위 그래프는 하나로 연결된 하나의 그래프이다. 모든 노드는 BFS 탐색의 시작점이 될 수 있다. BFS를 통해 방문한 노드는 방문 기록을 남기게 되고, 시작점이 되지 못한다. 시작점이 없을 때까지 BFS를 수행하고, 문제의 답은 BFS를 수행한 횟수가 된다. 개인적으로 이 문제를 비롯한 기본 bfs, dfs문제들이 왜 level 3인지 이해가 되지 않는다. 최종 코드 #include #include #include using namespace std; vector adj[201]; bool visited[201]; void bfs(int start){ queue que; que.push(start); visited[start..

[백준 1649] 택시 (C++)

1649번: 택시 첫 번째 줄에 교차로의 개수인 N(1 ≤ N ≤ 1,000)과 도로의 개수 M이 주어진다. 그 다음 M개에 줄에는 도로의 정보를 알려주는 시작점과 끝점이 주어진다. 다음 줄에는 시작점 A와 끝점 B, 그리고 방 www.acmicpc.net 조건 N개의 노드가 존재하고 노드들은 서로 단방향으로 연결되어 있다. A라는 노드에서 출발해 다시 A노드로 돌아올 수 없다. U -> V 연결이 있다면 V -> U 연결은 있을 수 없다. A에서 B로 가야 한다. 가는 도중에 C1, C2 ... Cn 노드를 거쳐가야 한다. 이때 중간 노드의 방문 순서는 중요하지 않다. 요구사항 A에서 B로 가기 위한 경로의 수를 출력하라. A에서 B로 가는 모든 경로를 탐색해보는 top-down DP로 풀려다가 도저히..

[백준 1726] 로봇 (c++)

1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 오랜만에 푼 알고리즘 문제 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 두 가지 조건을 만족하며 출발 로봇이 도착지점의 상태와 같아질 때까지 이동시키는 프로그램을 구현하면된다. 나는 K칸 만큼 움직일 때 갈 수 없는 모든 조건에 break를 걸어주어서 많이 틀렸다. 벽에 막혀서 갈 수 없는 경우에만 ..

[백준 16681] 등산 C++

16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 다익스트라 시작점은 항상 1이고 도착점은 항상 N이다. 시작점에서 도착점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다. 도착점에서 시작점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다. 임의의 가운데 정점을 잡고 해당 정점이 시작점과 도착점 모두와 연결되어있다면 위 2개의 다익스트라를 통해서 시작점과 연결된 최단거리는 자연스럽게 높이가 증가하는 최단거리가 구해지고, 임의의 정점에서 도착점으로 가는 최단거리는 높이가 감소하..

선거 공약 (PROMISES)

algospot.com :: PROMISES 선거 공약 문제 정보 문제 경제가 침체기에 빠졌을 때 정치인들이 흔히 내거는 공약으로 대규모 토목 공사를 통한 경기 부양책이 있습니다. 이번에 집권당에서는 향후 N 년간 1년에 하나씩 전국 algospot.com 플로이드-와샬 문제 설명 더보기 우선 기존에 있던 고속도로들을 가지고 플로이드 알고리즘을 통해서 최단거리를 구해준다. 그리고 새로운 고속도로(a에서 b로 가는)가 건설 될 때마다 현재 최단거리와 비교해서 비용이 같거나 오히려 더 크다면 해당 고속도로를 설치할 필요가 없다. 하지만 새로운 고속도로를 설치하는게 이득이 된다면 a에서 b로 가는 고속도로를 추가하고 플로이드 알고리즘을 통해서 모든 간선의 최소비용을 갱신해 준다. r에서 c로 가는 비용을 갱신..

Sorting Game (SORTGAME)

algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com BFS, 최단거리 처음보는 유형의 문제. 신기한 문제 지금까지 백준에서 푼 bfs문제들은 그래프의 정점이나 좌표정도만 queue에 넣고 bfs를 수행했는데 이 문제는 순열 벡터를 que에 넣으면서 해당 순열을 몇 번째로 방문했는지 bfs를 통해서 체크한다. 1. 중복되는 숫자는 없기 때문에 숫자의 크기가 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같다. ex) {37, 80, 12, 25}와 {3, 4, 1, 2}는 상..

[백준 1005] ACM Craft C++

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 1. 문제해결 아이디어 indegree를 활용한 위상 정렬을 하는 문제이다. 위 그림에서 각각의 phase는 다음 phase로 넘어가기위해 모두 해결해야하는 과제와도 같다. 예를 들어서 phase2에서 phase3로 넘어가려면 phase2에 있는 건물을 모두 건설해야 넘어갈 수 있다. 따라서 phase2에서 가장 오래걸리는 건물이 해당 phase에서 걸리는 시간이 되고, 이전 phase의 최대 시간만큼만 next phase의..

Minimum Spanning Tree (MST) - Kruskal

크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인드(Union-Find)에 대한 이해 8할 Edge 구조체 설계 2할? find_topnode() 를 통해서 현재 정점(Vertax)의 최상단 노드(부모노드) 를 알 수 있다. Node[Vertax]의 값이 음수이면 Vertax가 부모노드임을 의미한다 is_cycle()을 통해서 a와 b 정점이 서로 같은 노드인지 확인한다(find_topnode() 사용) Union_node()를 통해서 a 와 b정점을 하나로 병합한다 a, b정점의 부모 노드가 가지는 값은 항상 음수이다. 값이 더 작을수록 더 많은..

[백준 9466] 텀프로젝트 C++

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 를 이용해서 사이클을 이루는지 확인하는 문제 사이클을 찾는 문제다 보니 처음에 union-find를 사용해서 풀었다.. 결과는 시간초과! 틀린 코드 더보기 #include using namespace std; int student[100001]; bool visited[100001]; int makeUnion(int st, int p){ if(student[p] == st) return student[p] = 0; return student[p] = makeU..