문제 링크 성능 요약 메모리: 273764 KB, 시간: 1044 ms 분류 그래프 이론, 최소 공통 조상, 트리 제출 일자 2024년 3월 29일 16:40:19 문제 설명 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. 출력 M개의 줄에 차례대로 입력받은 두 정점..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net DFS와 BFS는 아직 좀 어렵다... 많은 연습을 필요로 할 듯 하다~ DFS n = int(input()) v = int(input()) graph = [[] for i in range(n+1)] visited = [0] * (n+1) for i in range(v): a, b = map(int, input().split()) graph[a] += [b] graph[b] += [a] def dfs(..

https://youtu.be/7C9RgOcvkvo?si=HMjH9vrqOZXbSek7 본 내용은 위의 유투브를 참고해서 작성했음을 밝힙니다! 음료수 얼려먹기 문제 해결 아이디어 문제 풀이 # DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문 def dfs(x, y): # 주어진 범위를 벗어나는 경우에는 즉시 종료 if x = n or y = m: return False # 현재 노드를 아직 방문하지 않았다면 if graph[x][y] == 0: # 해당 노드 방문 처리 graph[x][y] = 1 # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출 dfs(x - 1, y) dfs(x, y - 1) dfs(x + 1, y) dfs(x, y + 1) return True return False ..

https://youtu.be/7C9RgOcvkvo?si=HMjH9vrqOZXbSek7 본 내용은 위 유투브를 참고해서 작성했음을 밝힙니다! DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같음 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복함. # DFS 메서드 정의 def dfs(graph, v, visited): ..

https://youtu.be/7C9RgOcvkvo?si=934r_SLkImsdK3b- 본 내용은 위 유투브를 참고했음을 밝힙니다. 재귀함수 재귀함수(Recursion Function)란 자기 자신을 다시 호출하는 함수 단순한 형태의 재귀 함수 예제 '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력함 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력됨 def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() 별도로 while/for 를 사용하지 않아도 반복문 사용 가능. but, 재귀 함수의 종료 조건을 반드시 명시해야 함. 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출됨. 종류 ..