문제풀이/그래프

https://www.acmicpc.net/problem/21316코드from collections import defaultdict, dequegraph = [[] for _ in range(13)]for _ in range(12): x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x)def bfs(start): dist = [12]*13 dist[start] = 0 q = deque([start]) while q: now = q.popleft() for nx in graph[now]: if dist[nx] > dist[now]+1: ..

https://www.acmicpc.net/problem/22856 코드const fs = require("fs");const filePath = process.platform === "linux" ? "dev/stdin" : "./input.txt";const [n, ...arr] = fs .readFileSync(filePath) .toString() .trim() .split(/\s/) .filter((item) => item != "") .map((item) => +item);const graph = Array.from(Array(n + 1), () => new Array(2).fill(-1));for (let i = 0; i { if (graph[now][0] !== -1 && !..

https://www.acmicpc.net/problem/19535코드from math import combn = int(input())children = [0]*(n+1)graph = []for _ in range(n-1): u, v = map(int, input().split()) children[u] += 1 children[v] += 1 graph.append((u, v))d_num, g_num = 0, 0# ㄷfor u, v in graph: d_num += (children[u]-1)*(children[v]-1)# ㅈfor i in range(1, n+1): if children[i] >= 3: g_num += comb(children[i], 3)i..

11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 코드 from collections import deque import sys input = sys.stdin.readline n = int(input()) graph = [[] for _ in range(n+1)] # 노드 간 연결 for _ in range(n-1): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) # 각 노드 레벨 구하기(BFS) level = [-1]*(n+..

22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 문제 노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다. 유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다. 그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직..