파이썬
-
알고리즘: 백준 1504번 특정한 최단 경로 (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 12. 14:41
1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net import sys import heapq read = sys.stdin.readline N, E = map(int, read().split()) graph = {i:[] for i in range(1, N+1)} for _ in range(E): a, b, c = map(int, read().split()) graph[a].append([b,c]) graph[b].append([a,c]) v1, v2 = map(in..
-
알고리즘: 백준 1238번 파티 (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 11. 20:07
1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import sys import heapq read = sys.stdin.readline N, M, X = map(int, read().split()) graph = {i: []for i in range(1, N+1)} # 각 마을에서 X로 가는 방향 그래프 graph2 = {i: []for i in range(1, N+1)} # X에서 각 마을로 가는 그래프 for _ in range(M): s, e, l = map(int, re..
-
알고리즘: 백준 1261번 알고스팟 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 11. 18:03
1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net import sys import heapq read = sys.stdin.readline m, n = map(int, read().split()) maze = [list(map(int,read().strip()))for i in range(n)] visit = [[0 for _ in range(m)] for _ in range(n)] def dijkstra(): dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] hq = [..
-
알고리즘: 백준 1753번 최단경로 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 11. 15:25
1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net import sys import heapq read = sys.stdin.readline N = int(read()) M = int(read()) graph = {i:[] for i in range(1, N+1)} for i in range(1, M+1): s, e, v = map(int, read().split()) graph[s].append([e,v]) start, end = map(int, read().split()) INF =..
-
알고리즘: 백준 11724번 연결 요소의 개수 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 8. 10:57
11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net import sys read = sys.stdin.readline n, m = map(int, read().split()) graph = {} for i in range(n): graph[i+1] = [] for _ in range(m): u, v = map(int, read().split()) graph[u].append(v) graph[v].append(u) global count count = 0..
-
알고리즘: 백준 1012번 유기농 배추 (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 7. 18:47
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net import sys read = sys.stdin.readline case = int(read()) def sol(): global count count = 0 m, n, bae = list(map(int, read().split())) box = [[0 for _ in range(m)] for _ in range(n)] for _ in range(bae): x, y = list(map(int, read().split())) box[y][x] = 1 for i in rang..
-
알고리즘: 백준 1260번 DFS와 BFS (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 7. 17:44
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import sys from collections import deque read = sys.stdin.readline n, m, v = list(map(int, read().split())) graph ={} for i in range(n): graph[i+1] = deque() for i in range(m): x, y = deque(map(int, read().split())) graph[x].append(y) grap..
-
알고리즘: 백준 7576번 토마토 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 6. 11:43
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net import sys from collections import deque read = sys.stdin.readline x, y = list(map(int, read().split())) box = [] q_y = deque() q_x = deque() for i in range(y): tmp = list(map(int, read().split())) box.append(tmp) count_1 = 0 for i in range(len(box)):..