본문 바로가기
728x90
반응형

그래프

Algorithm & Data Structure 2022. 8. 18. 백준 - 1956번(다익스트라) https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net import sys from heapq import heappush,heappop v,e = map(int,sys.stdin.readline().split()) arr = [[] for _ in range(v+1)] ans = [[float('inf') for _ in range(v + 1)] for _ in range(v+1)] q = [] for _ in ra..
Algorithm & Data Structure 2022. 8. 18. 백준 - 2573번(구현, 그래프) https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net import copy import sys from collections import deque # 조건에 따라 빙산이 녹는 것을 구현 여기서 주의점은 얼음은 동시에 녹기 때문에 # 옆에 있는 빙산이 녹아서 0이 되더라도 당장은 영향을 받지 않는다. def check(x,y): dx = [1,-1,0,0] dy = [0,0,1,-1] cnt = 0 for i in range(4): nx = x..
Algorithm & Data Structure 2022. 8. 18. 백준 - 1043번(그래프) https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net import sys from collections import deque def TrueOrFalse(ans): n, m = map(int, sys.stdin.readline().split()) known = deque(list(map(int, sys.stdin.readline().split()))) known.popleft() check = [False for _ in range(n + 1)] party ..
Algorithm & Data Structure 2022. 8. 16. 백준 - 1717번(유니온 파인드, 재귀, 집합) https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 자체가 이해가 어렵지는 않은 문제다. 이 문제를 풀기 위해서는 유니온 파인드가 뭔지 알아야 한다. 그래프 풀이법의 일종으로 볼 수 있다. 노드들을 합치고(union), 부모를 찾아준다(find) 일련의 과정은 다음과 같다. 1. 원소 두 개를 입력받고 Union 함수를 호출한다. 2. 입력받은 원소의 부모를 find 함수를 이용해서 '재귀적으로' 찾아..
Algorithm & Data Structure 2022. 8. 14. 백준 - 2638번(BFS,구현) https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net import sys from collections import deque n,m = map(int,sys.stdin.readline().split()) arr = [] for _ in range(n): arr.append(list(map(int,sys.stdin.readline().split()))) dx = [1,-1,0,0] dy = [0,0,1,-1] def bfs(): q = ..
Algorithm & Data Structure 2022. 8. 6. 백준 - 9370번(다익스트라, DP) https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net import sys from collections import deque def dajik(st, ed): if st == ed: return 0 q = deque([]) q.append([0, st]) dist = [float('inf')] * (n + 1) while q: now_value, st = q.popleft() for i in arr[st]: if now_value + i[1]..
Algorithm & Data Structure 2022. 8. 6. 백준 - 1504번(다익스트라, DP) https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net import sys import heapq n,e = map(int,sys.stdin.readline().split()) arr = [[] for _ in range(n+1)] for _ in range(e): a,b,c = map(int,sys.stdin.readline().split()) arr[a].append([b,c]) arr[b].append..
728x90
반응형

티스토리툴바