알고리즘/Graph 그래프8

• 

  [프로그래머스] 합승 택시 요금 - java 나의 풀이 import java.util.*; class Solution { static final int MAX = 20000001; static ArrayList[] graph; public int solution(int n, int s, int a, int b, int[][] fares) { int answer = MAX; graph = new ArrayList[n+1]; for(int i=0; ia & i->b 까지 따로간다. answer = Math.min(answer, start[i] + startA[i] + startB[i]); } return answer; } public int[] dijkstra(int start, int n){ int[] dist = new int[n+1]; // di.. 알고리즘/Graph 그래프 2023. 4. 24.

• 

  [백준] 1753번: 최단경로 - java 나의풀이 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static class Node implements Comparable{ int num; int weight; public .. 알고리즘/Graph 그래프 2023. 3. 2.

• 

  [백준] 2250번: 트리의 높이와 너비 - java 주의할점 : 루트가 1번이라는 보장X, 입력으로 주어지는 노드들이 1~N번 순서대로 주어지는 보장X 나의코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.Set; import java.util.StringToke.. 알고리즘/Graph 그래프 2023. 2. 27.

• 

  [백준] 1167번: 트리의 지름 - java 트리 지름 처음에는 아무 생각 없이 1~v개의 모든 정점에 대하여 가장 먼 노드를 찾기 위해 DFS를 실행했다. 그러나 이 문제는 V가 최대 100000개로, 모든 노드에 대해 DFS를 실행하였을 때 O(n^2) 로 100000x100000 이라는 시간초과를 낳게 되었다. 따라서 트리의 지름에 대해 더 깊은 이해가 필요하였다. (출처) 트리의 지름에 대한 고찰 : https://mygumi.tistory.com/226 트리란 무엇인가? 트리란 노드 N개에 간선 N-1개가 싸이클 없이 존재하는 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 .. 알고리즘/Graph 그래프 2023. 2. 18.

• 

  [백준] 3665번: 최종 순위 - 파이썬(python) 나의 풀이 from collections import deque T = int(input()) for _ in range(T): n = int(input()) graph = [[False]*(n+1) for _ in range(n+1)] last_year = list(map(int, input().split())) # 작년의 순위 indegree = [0] * (n+1) # 진입차수 for i in range(n): for j in range(i+1,n) : graph[last_year[i]][last_year[j]] = True indegree[last_year[j]] += 1 # j의 진입차수 1증가 m = int(input()) # 상대적인 등수가 바뀐 쌍의 수 for i in range(m) : .. 알고리즘/Graph 그래프 2022. 10. 21.

• 

  [벡준] 2887번: 행성 터널 - 파이썬(python) 틀린 풀이 import heapq def find_parent(parent, x) : if parent[x] != x : parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, i,j) : a = find_parent(parent, i) b = find_parent(parent, j) if a < b : parent[b] = a else : parent[a] = b N = int(input()) arr = [] q = [] parent = [i for i in range(N)] for _ in range(N) : x,y,z = map(int, input().split()) arr.append((x,y,z)) .. 알고리즘/Graph 그래프 2022. 10. 21.

• 

  [프로그래머스] 순위 - 파이썬(python) 나의 풀이 from collections import deque def find_person(winner, loser, node) : q = deque() visited = [False] * (len(winner)+1) for i in winner[node] : q.append(i) while q : x = q.popleft() for i in winner[x] : if not visited[i] : # 아직 탐색하지 않은 선수라면 visited[i] = True winner[node].add(i) # 내가 이길 수 있는 사람에 i를 추가 loser[i].add(node) # i가 지는 사람에 나를 추가 q.append(i) def solution(n, results): winner = [set([]) .. 알고리즘/Graph 그래프 2022. 9. 25.

• 

  [프로그래머스] 가장 먼 노드 - 파이썬(python) 나의 풀이 from collections import deque def solution(n, edge): visited = [-1] * (n+1) graph = [[] for _ in range(n+1)] q = deque() for x,y in edge : graph[x].append(y) graph[y].append(x) q.append(1) visited[1] = 0 while q : node = q.popleft() for i in graph[node] : if visited[i] == -1 : visited[i] = visited[node] + 1 q.append(i) max_cnt = max(visited) return visited.count(max_cnt) BFS 로 푼 문제이다. 1번 노.. 알고리즘/Graph 그래프 2022. 9. 25.