전체 글
11725번-트리의 부모 찾기
문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근방법 1) 접근 사고 깊이 우선 탐색에서 가장 깊은 탐색을 진행한 뒤 재귀가 끝난 경우를 노드의 현재 번호값에 저장하면 되는 문제였습니다. 2) 시간 복잡도 3) 실수 4) 배운점 5) PS 정답 코드 #include using namespace std; int n; const int MAX = 100005; vector edge[MAX]; bool visited[MAX]; int ret[MAX]; void DFS(int cur) { visited[c..
2606번-양
문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 접근방법 1) 접근 사고 1. DFS 탐색을 통해 1번 바이러스와 연결된 간선들을 탐색해주면 됩니다. 2. 바이러스의 숙주인 1번은 제외하고 출력해야 합니다. 2) 시간 복잡도 3) 실수 4) 배운점 5) PS 정답 코드 #include using namespace std; int n, m, ans; const int MAX = 105; vector board[MAX]; bool visited[M..
3184번-양
문제 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 접근방법 1) 접근 사고 1. 울타리가 아닌 영역을 탐색한다. 2. 울타리가 아닌 영역의 양과 늑대수를 측정한다. 3. 양이 늑대수보다 클 경우에는 양의 결과를 반환하는 변수에 양의 수를 더해주고 아닌 경우에는 늑대의 결과를 반환하는 변수에 늑대의 수를 더해준다. 2) 시간 복잡도 O(v + e) 3) 실수 4) 배운점 5) PS 정답 코드 #include using namesp..