알고리즘/백준
[백준]230410-230416 문제풀이(Python)
stubborngastropod
2023. 4. 20. 17:52
728x90
1774. 우주신과의 교감
import sys
input = sys.stdin.readline
def find(x):
if parents[x] != x:
parents[x] = find(parents[x])
return parents[x]
def union(x, y):
x = find(x)
y = find(y)
if x < y:
parents[y] = x
else:
parents[x] = y
N, M = map(int, input().split())
gods = []
for _ in range(N):
r, c = map(int, input().split())
gods.append((r, c))
dist = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
for j in range(N):
d = ((gods[i][0] - gods[j][0])**2 + (gods[i][1] - gods[j][1])**2)**(1/2)
dist[i+1][j+1] = d
for i in range(M):
a, b = map(int, input().split())
dist[a][b] = 0
distance = []
for i in range(1, N + 1):
for j in range(1, N + 1):
distance.append((dist[i][j], i, j))
distance.sort()
parents = [i for i in range(N + 1)]
ans = 0
for i in range(len(distance)):
d, a, b = distance[i]
if a == b:
continue
if find(a) != find(b):
union(a, b)
ans += d
print(f'{ans:.2f}')MST 문제. 이미 연결된 노드들의 가중치를 0으로 설정해주고 유니온 파인드를 적용해주면 된다.
9466. 텀 프로젝트
import sys
input = sys.stdin.readline
sys.setrecursionlimit(999999)
def dfs(now):
global ans
visited[now] = True
cycle.append(now)
if visited[lst[now]]:
if lst[now] in cycle:
ans += cycle[cycle.index(lst[now]):]
return
else:
dfs(lst[now])
T = int(input())
for tc in range(T):
N = int(input())
lst = [0] + list(map(int, input().split()))
visited = [False] * (N + 1)
ans = []
for i in range(1, N + 1):
if visited[i]:
continue
cycle =[]
dfs(i)
print(N - len(ans))dfs를 해주다가 방문했던 노드에 도착한다면, 그 노드가 사이클을 이룰 수 있는 노드인지 확인하고 정답에 포함시킬지를 결정한다.
5373. 큐빙
import sys
input = sys.stdin.readline
def rotate(plane, direction):
if direction == '-':
plane[0][0], plane[0][1], plane[0][2], plane[1][0], plane[1][2], plane[2][0], plane[2][1], plane[2][2]=\
plane[0][2], plane[1][2], plane[2][2], plane[0][1], plane[2][1], plane[0][0], plane[1][0], plane[2][0]
else:
plane[0][2], plane[1][2], plane[2][2], plane[0][1], plane[2][1], plane[0][0], plane[1][0], plane[2][0]= \
plane[0][0], plane[0][1], plane[0][2], plane[1][0], plane[1][2], plane[2][0], plane[2][1], plane[2][2]
return plane
T = int(input())
for tc in range(T):
N = int(input())
lst = list(input().split())
u = [['w'] * 3 for _ in range(3)]
d = [['y'] * 3 for _ in range(3)]
l = [['g'] * 3 for _ in range(3)]
r = [['b'] * 3 for _ in range(3)]
f = [['r'] * 3 for _ in range(3)]
b = [['o'] * 3 for _ in range(3)]
for i in range(N):
plane, direction = lst[i][0], lst[i][1]
if plane == 'L':
if direction == '+':
u[0][0], u[1][0], u[2][0], f[0][0], f[1][0], f[2][0],\
d[0][0], d[1][0], d[2][0], b[0][0], b[1][0], b[2][0] =\
b[0][0], b[1][0], b[2][0], u[0][0], u[1][0], u[2][0],\
f[0][0], f[1][0], f[2][0], d[0][0], d[1][0], d[2][0]
l = rotate(l, '+')
else:
b[0][0], b[1][0], b[2][0], u[0][0], u[1][0], u[2][0], \
f[0][0], f[1][0], f[2][0], d[0][0], d[1][0], d[2][0] = \
u[0][0], u[1][0], u[2][0], f[0][0], f[1][0], f[2][0], \
d[0][0], d[1][0], d[2][0], b[0][0], b[1][0], b[2][0]
l = rotate(l, '-')
if plane == 'R':
if direction == '-':
u[0][2], u[1][2], u[2][2], f[0][2], f[1][2], f[2][2], \
d[0][2], d[1][2], d[2][2], b[0][2], b[1][2], b[2][2] = \
b[0][2], b[1][2], b[2][2], u[0][2], u[1][2], u[2][2], \
f[0][2], f[1][2], f[2][2], d[0][2], d[1][2], d[2][2]
r = rotate(r, '-')
else:
u[0][2], u[1][2], u[2][2], f[0][2], f[1][2], f[2][2], \
d[0][2], d[1][2], d[2][2], b[0][2], b[1][2], b[2][2] = \
f[0][2], f[1][2], f[2][2], d[0][2], d[1][2], d[2][2], \
b[0][2], b[1][2], b[2][2], u[0][2], u[1][2], u[2][2]
r = rotate(r, '+')
if plane == 'U':
if direction == '+':
b[2][0], b[2][1], b[2][2], r[0][0], r[1][0], r[2][0], \
f[0][2], f[0][1], f[0][0], l[2][2], l[1][2], l[0][2] = \
l[2][2], l[1][2], l[0][2], b[2][0], b[2][1], b[2][2], \
r[0][0], r[1][0], r[2][0], f[0][2], f[0][1], f[0][0]
u = rotate(u, '+')
else:
l[2][2], l[1][2], l[0][2], b[2][0], b[2][1], b[2][2], \
r[0][0], r[1][0], r[2][0], f[0][2], f[0][1], f[0][0] = \
b[2][0], b[2][1], b[2][2], r[0][0], r[1][0], r[2][0], \
f[0][2], f[0][1], f[0][0], l[2][2], l[1][2], l[0][2]
u = rotate(u, '-')
if plane == 'D':
if direction == '-':
b[0][0], b[0][1], b[0][2], r[0][2], r[1][2], r[2][2], \
f[2][2], f[2][1], f[2][0], l[2][0], l[1][0], l[0][0] = \
l[2][0], l[1][0], l[0][0], b[0][0], b[0][1], b[0][2], \
r[0][2], r[1][2], r[2][2], f[2][2], f[2][1], f[2][0]
d = rotate(d, '-')
else:
l[2][0], l[1][0], l[0][0], b[0][0], b[0][1], b[0][2], \
r[0][2], r[1][2], r[2][2], f[2][2], f[2][1], f[2][0] = \
b[0][0], b[0][1], b[0][2], r[0][2], r[1][2], r[2][2], \
f[2][2], f[2][1], f[2][0], l[2][0], l[1][0], l[0][0]
d = rotate(d, '+')
if plane == 'F':
if direction == '+':
l[2][0], l[2][1], l[2][2], u[2][0], u[2][1], u[2][2], \
r[2][0], r[2][1], r[2][2], d[0][2], d[0][1], d[0][0] = \
d[0][2], d[0][1], d[0][0], l[2][0], l[2][1], l[2][2], \
u[2][0], u[2][1], u[2][2], r[2][0], r[2][1], r[2][2]
f = rotate(f, '+')
else:
d[0][2], d[0][1], d[0][0], l[2][0], l[2][1], l[2][2], \
u[2][0], u[2][1], u[2][2], r[2][0], r[2][1], r[2][2] = \
l[2][0], l[2][1], l[2][2], u[2][0], u[2][1], u[2][2], \
r[2][0], r[2][1], r[2][2], d[0][2], d[0][1], d[0][0]
f = rotate(f, '-')
if plane == 'B':
if direction == '-':
l[0][0], l[0][1], l[0][2], u[0][0], u[0][1], u[0][2], \
r[0][0], r[0][1], r[0][2], d[2][2], d[2][1], d[2][0] = \
d[2][2], d[2][1], d[2][0], l[0][0], l[0][1], l[0][2], \
u[0][0], u[0][1], u[0][2], r[0][0], r[0][1], r[0][2]
b = rotate(b, '-')
else:
d[2][2], d[2][1], d[2][0], l[0][0], l[0][1], l[0][2], \
u[0][0], u[0][1], u[0][2], r[0][0], r[0][1], r[0][2] = \
l[0][0], l[0][1], l[0][2], u[0][0], u[0][1], u[0][2], \
r[0][0], r[0][1], r[0][2], d[2][2], d[2][1], d[2][0]
b = rotate(b, '+')
for i in u:
print(*i, sep='')더 이상의 자세한 설명은 생략한다.......
16562. 친구비
import sys
input = sys.stdin.readline
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
x = find(x)
y = find(y)
if lst[x] <= lst[y]:
parent[y] = parent[x]
else:
parent[x] = parent[y]
N, M, K = map(int, input().split())
lst = [0] + list(map(int, input().split()))
parent = [i for i in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
union(a, b)
for i in range(1, N + 1):
find(i)
friends = list(set(parent[1:]))
cost = 0
for i in friends:
cost += lst[i]
if cost > K:
print("Oh no")
else:
print(cost)유니온 파인드를 하는데, 각 노드의 부모를 정해줄 때 인덱스가 작은 순이 아니라 친구비가 작은 순으로 결정해준다.
1654. 랜선자르기
import sys
input = sys.stdin.readline
K, N = map(int, input().split())
lst = []
for _ in range(K):
lst.append(int(input()))
l, r = 0, max(lst)
ans = 1
while l <= r:
m = (l + r) // 2
if not m:
break
cnt = 0
for i in lst:
cnt += i // m
if cnt >= N:
ans = m
l = m + 1
else:
r = m - 1
print(ans)간단한 이분탐색 문제. 코테 기출이라 이전에 풀었지만 다시 풀어봤다. 그 김에 이전에 짰던 정답 코드와 비교해봤는데 감회가 새로웠다.
왼쪽이 2월에 풀었던 코드, 오른쪽이 지금 코드인데 간결함이 확 다르다. 알고리즘 실력 되게 안 느는 줄 알았는데 생각보다 많이 성장한 것 같아서 웃기다.
2623. 음악 프로그램
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
N, M = map(int, input().split())
D = defaultdict(int)
adj = [[] for _ in range(N + 1)]
for _ in range(M):
n, *singers = map(int, input().split())
for i in range(1, n):
if singers[i] not in adj[singers[i-1]]:
adj[singers[i-1]].append(singers[i])
D[singers[i]] += 1
q = deque()
ans = []
for i in range(1, N + 1):
if not D[i]:
ans.append(i)
q.append(i)
while q:
now = q.popleft()
for nxt in adj[now]:
if D[nxt]:
D[nxt] -= 1
if not D[nxt]:
ans.append(nxt)
q.append(nxt)
if sum(D.values()):
print(0)
else:
print(*ans, sep='\n')위상 정렬 기본 문제. 각 노드들에 도달하기 위해 거쳐야 하는 직전 노드들의 수를 딕셔너리에 저장해놓고 해당 딕셔너리의 값이 0이 되었을 때 큐에 집어넣어 주는 식으로 진행한다. 마지막에는 딕셔너리의 값이 남아있는지 여부로 정답 존재 여부를 판단했다.
코테 직전에 풀어보고 싶었던 문제들을 풀었는데 나쁘지 않았던 것 같다. 코테는... 2~2.5솔인 것 같은데 결과가 언제 나올지 몰라 불안하다.
728x90