룰루랄라 알고리즘

일반적인 바텀업 형식이 아니라 탑다운 형식의 문제

원래는 브루트 포스로 하나하나 대입해서 풀었는데 코드도 더럽고 내 취향이 아니라 다르게 풀어봤음 DFS를 이용하여 값을 더해가는 풀이 idx = 1 일 때(즉, 두개의 블럭을 선택했을 때) 새로운 블럭에서 다음 블럭을 탐색하는 것이 아니라 다시 기존블럭에서 탐색하게 만들면 ㅗ,ㅏ,ㅓ,ㅜ 모양을 만들 수 있다. 가지치기 하는 코드 2차원배열에서 최대값을 찾아서 max(map(max, graph)) 선택할 수 있는 남은 블럭의 갯수만큼 (3 - idx) 곱해주고 현재 누적합 total 에 더해서 max_result 와 비교해주는 방식 가지치기 안하니까 시간초과 나옴 ***방문처리 주의하자***

그래프의 순환을 구해서 나머지 트리에서 순환그래프까지의 거리 구하기

A - B B - C C - D D - E 즉 트리의 깊이가 4가 되는 트리가 있다면 문제의 조건을 만족함 dfs 함수에서 깊이를 나타내는 count 변수를 넘겨주면서 count==4가 된다면 1을 출력하고 프로그램을 종료

parents[i] : 각 노드의 부모 노드 저장 graph[i] : 노드 정보 저장 graph[i].append(parents[i]) check와 del_node 함수를 통해 graph[delete] 와 graph안에 있는 delete 즉(graph[i][0] = delete) 모두 제거 dfs 함수 for문에서 tree가 비어 있다면 자식 노드가 없는 리프노드 이므로 result+=1

이 방법 말고도 stack을 pop하여 마지막 값 -1을 없애버려도 되지않을까

트리의 지름은 루트(또는 아무 노드)에서 가장 먼 노드를 찾고 그 노드부터 가장 먼 노드를 찾아 길이를 구하면 됨 dfs(node_index, result2)를 수행 한 후에는 자기 자신으로의 가중치를 0으로 초기화 한다.

그래프를 따라 번갈아가면서 색을 칠하다가 이미 방문했던 정점이 이전 정점 색과 같은 색이라면 이분그래프가 아니다. 색은 dfs 함수에서 group과 -group을 번갈아 넘겨주면서 1과 -1로 표현한다. result를 True로 선언 하고 dfs 함수에서 만약 정점의 색이 같다면 False를 리턴해 result에 저장 마지막에 result의 값에 따라 이분그래프 판별 출력 *주의* 재귀 함수 dfs에서 return을 했을 때 현재 돌고있는 함수만 종료 된것이지 dfs함수 전체가 종료되는 것이 아니다. return False를 하더라도 종료되는 것은 dfs의 전체 과정이 아니라 딱 현재 실행되고 있는 함수뿐이다. 처음에 전역에서 호출된 dfs와 그 dfs가 호출한 dfs는 서로 다른 함수이며, 그 dfs가..

정점의 개수 N, 간선의 개수 M 1. 양방향 노선이므로 graph[a][b] ,graph[b][a] 모두 1로 초기화 2. 자기 자신으로 가는 단계는 0으로 초기화 3. 기존의 최저 단계와 a가 k를 거쳐 b로 가는 단계를 비교해 최솟값 저장 4. graph[i] 의 합이 가장 적은 사람 즉 케빈베이컨의 합이 가장 적고 인덱스가 가작 작은 사람 출력