접근 최단거리를 찾는 문제중에서 특정 정점에서 특정 정점까지 가는 문제라 bfs, 다익스트라 알고리즘으로 풀 생각을 했다. 가중치가 없어 bfs로도 풀수있겠다는 생각을 했지만 경로 알고리즘을 학습하고 싶어 시간 제한을 생각하지않고 다익스트라, 플로이드 워셜으로 풀어봤다. 플로이드 워셜(시간초과) import sys input = sys.stdin.readline n, m , t = map(int,input().split()) M = [[101 for _ in range(n)] for _ in range(n)] for i in range(m): s, f, v = map(int,input().split()) M[s-1][f-1] = v for i in range(n): M[i][i] = 0 for k in ..

접근 1.트리를 어떻게 표현해야할까. 배열 ? 그래프? 예제 입력 케이스를 보니 그래프가 편할거 같아서 선택 2.어떤 정점부터 그래프 탐색을 진행해야 지름을 구할 수 있을까. 리프 노드에서 리프 노드까지일텐데 그래프의 length가 1인 경우를 구하면 되려나? 1번 노드에 2, 3, 4, 5 , 6, 7 번 노드가 연결된 경우를 생각해보자 (1) 1 2 3 4 5 6 (2) (3) (4) (5) (6) (7) 이런 그래프가 있다면 (7) -> (1) -> (6) 을 방문하는 경우가 최대인데 안되겠다. 근데 어떤곳에서 그래프 탐색을 탐색을 하면 가장 먼 노드가 구해지고 그 노드부터 가면 최대값이 구해지겠다. bfs와 dfs로 둘다 풀어보자! 나의 코드1 (dfs) import sys input = sys...

접근 브루트포스로 모든 경우 탐색을 해서 최소 비용을 알아내야겠다. dfs로 탐색해서 최소값을 업데이트하고 최소값을 비교해가면서 최소값보다 합이 커지면 처음 단계로 돌아가야겠다. 나의 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) n = int(input()) M = [list(map(int,input().split())) for _ in range(n)] minvalue = sys.maxsize def dfs(cnt,value,p): global minvalue if value >= minvalue: return if cnt == n: minvalue = min(value,minvalue) else: for i in rang..

1. Folder 만들기 2. Folder 접근 control+s -> 이름 저장 (! 이름이 반드시 문자로 시작해야하고 기존 함수와 겹치는 이름이면 안된다.)

접근 1. 진실을 아는 사람이 파티에 참여하면 거짓을 말하지 못한다. 2. 또다른 파티에서는 과장된 이야기를 들었을 때도 거짓말쟁이로 알려지게 된다. 진실을 아는 사람 그룹을 만들고 진실을 아는 사람이 파티에 있을때 bfs를 이용해 연관되어있는 사람을 모두 진실을 아는 사람 그룹에 넣는다. 그 후 해당 그룹에 인원들이 모두 없는 파티만 세어준다. ex) 5 4 1 1 2 5 2 2 2 3 2 3 1 마지막에 1번이 있지만 1번이 진실을 알아 3번도 진실을 알게되고 2번도 3번이 알아서 진실을 알게되고 결국 5번도 진실을 알게된다. 따라서 마지막 1번이 발견했을때 그래프로 같은 집합에 있는 모든 사람을 진실을 아는 사람 그룹에 넣어야한다. 나의 코드 import sys input = sys.stdin.re..