from collections import Counter
def solution(points, routes):
'''
같은좌표에 로봇이 2대이상 모이는 개수 return하기
points: 포인트의 좌표를 나타내는 정수배열 -> 좌표는 100*100안에 있음
routes: [출발포인트,도착포인트] 정수배열
최단경로가 여러가지인 경우 행에서의 이동을 항상 먼저함.
장애물이 있는게 아니니깐 그냥 시작좌표, 도착좌표 불러온다음에 r좌표 먼저 맞춰주고 c좌표 맞춰주면 됨
굳이 BFS쓸필요 없음
1. points를 각 index+1을 key로 갖도록 dic로 만들기
2. routes를 하나씩 받아와서 dict[r[0]]부터 dict[[r[1]]]까지의 루트 인덱스를 리스트에 넣기
3. 모든 루트 인덱스에서 같은 시간에 같은 인덱스에 존재하는 개수 count하기
'''
time = 0
# points를 각 index+1을 key로 갖도록 dic로 만들기
dic = {i + 1: tuple(point) for i, point in enumerate(points)}
# 각 로봇의 전체 이동 경로
all_paths = []
for route in routes:
path = []
# 시작지점 dic에서 좌표 가져오기
start = dic[route[0]]
path.append(start)
# 도착지점 좌표 dic에서 가져오기
for i in range(len(route) - 1):
end = dic[route[i+1]]
# r 좌표 이동 먼저
#도착지점의 r좌표가 시작지점의r좌표보다 크면 delta가 1, 작으면 delta가 -1
delta = 1 if end[0] > start[0] else -1
#시작지점이랑 도착지점의 r좌표가 같아질때까지 이동
while start[0] != end[0]:
start = (start[0] + delta, start[1])
path.append(start)
# r좌표 먼저 이동시킨 다음에 c좌표 이동
# 도착지점의 c좌표가 시작지점의 c좌표보다 크면 delta가1, 작으면 delta가 -1
delta = 1 if end[1] > start[1] else -1
# start랑 end의 c좌표가 같아질때까지 이동
while start[1] != end[1]:
start = (start[0], start[1] + delta)
path.append(start)
all_paths.append(path)
#각 path중 가장 긴 길이를 time으로 저장해야됨
if len(path)>time:
time = len(path)
# 모든 경로에서 같은 시간에 같은 좌표에 존재하는 로봇의 개수세기
answer = 0
for t in range(time):
intersect = []
for p in all_paths:
# 각 경로의 길이(이동하는시간)은 모두 다르니깐 예외처리
if t < len(p):
intersect.append(p[t])
# 해당시간 t에 COunter로 동일한 위치의 로봇 개수 세기
count = Counter(intersect)
# count에서 val이 2이상이면 answer에다 1씩 추가하기
for c in count.keys():
if count[c] >= 2:
answer += 1
return answer
배울점
from collections import Counter
def solution(points, routes):
answer = 0
t = 0
cur_points = [] # 각 로봇들이 현재 위치 저장
targets = [] # 각 로봇들의 현재 목표 지점 저장
target_idx = [1] * len(routes) # 각 로봇들의 현재 목표 idx 저장
x = len(routes)
# 각 로봇의 현재 위치와 다음 목표 초기화
for i in range(x):
cur_points.append(points[routes[i][0] - 1])
targets.append(points[routes[i][1] - 1])
while any(idx != 0 for idx in target_idx):
for i in range(x): # 로봇 하나씩 선택
if target_idx[i] != 0 and cur_points[i] != targets[i]:
if cur_points[i][0] != targets[i][0]:
if cur_points[i][0] < targets[i][0]:
cur_points[i][0] += 1
else:
cur_points[i][0] -= 1
elif cur_points[i][1] != targets[i][1]:
if cur_points[i][1] < targets[i][1]:
cur_points[i][1] += 1
else:
cur_points[i][1] -= 1
# 목표 지점에 도달한 경우
if cur_points[i] == targets[i]:
if target_idx[i] != len(routes[0]) - 1:
target_idx[i] += 1
targets[i] = points[routes[i][target_idx[i]] - 1]
else: # 마지막 목표 지점에 도달한 경우
target_idx[i] = 0
counter = Counter(map(tuple, cur_points))
# 중복된 좌표 총 개수...?
t += 1
return answer
from collections import deque, defaultdict
def find_route(cur_point, tar_point):
dx = tar_point[1] - cur_point[1]
dy = tar_point[0] - cur_point[0]
if dy != 0:
dy = 1 if dy > 0 else -1
if dx != 0:
dx = 1 if dx > 0 else -1
return dx, dy
def compare(cur_point, tar_point):
if cur_point[0] == tar_point[0] and cur_point[1] == tar_point[1]:
return True
return False
def solution(points, routes):
answer = 0
# 자동 운송 시스템
# (r, c)와 같이 2차원 좌표 n개
# 운송 경로 m개의 포인트, 로봇은 할당된 포인트를 순서대로 방문
# 로봇은 x대, 1초마다 r좌표와 c좌표중 1개만큼 감소됨.
# 최단 경로로 이동하는데, 여러 가지일 경우, r좌표가 변하는 이동을 우선시함.
# 이동 중 같은 좌표에 2대 이상이 모인다면 충돌할 가능성 존재.
# 현재 설정대로 로봇이 움직인다면? 몇번이나 일어나는가?
# while문 내에서 robut의 수가 존재하는 동안,
# 1초마다 각 로봇을 움직이고, overlapped point가 있다면 answer += 1
# 각 로봇의 (현재 좌표, 목표 좌표는 순서만..)
# 이때 목표 좌표의 len이 0이면 해당 로봇은 안움직임.
robot_routes = deque([])
for route in routes:
start = route[0]
end = route[1:]
robot_routes.append((tuple(points[start-1]), end))
robot_num = len(routes)
robots = [False for _ in range(robot_num)]
# 0초일때도 계산..
tmp = defaultdict(int)
for cur, _ in robot_routes:
tmp[cur] += 1
for v in tmp.values():
if v > 1:
answer += 1
while sum(robots) != robot_num:
# 겹치는 좌표의 수 계산을 위한 dict
overlapped_point = defaultdict(int)
# 1 step
for i, route in enumerate(robot_routes):
if robots[i]:
continue
cur_point = route[0]
tar = route[1]
if len(tar) == 0:
robots[i] = True
continue
tar_point = points[tar[0] -1]
dx, dy = find_route(cur_point, tar_point)
# y축부터 이동.
if dy != 0:
cur_point = (cur_point[0] + dy, cur_point[1])
elif dx != 0:
cur_point = (cur_point[0], cur_point[1] + dx)
# 현재 목표 tar_point과 동일하다면?
# i) len(tar) == 1 이라면 현재 tar과 동일. -> 그 로봇은 끝남.
is_same = compare(cur_point, tar_point)
if is_same and len(tar) == 1:
robots[i] = True
tar = []
elif (is_same and len(tar) > 1):
tar = tar[1:]
overlapped_point[cur_point] += 1
robot_routes[i] = (cur_point, tar)
for v in overlapped_point.values():
if v > 1:
answer += 1
# print(f"{robots}")
# print(f"{robot_routes}")
# print(overlapped_point)
# answer += len(overlapped_point)
# print(f"answer : {answer}")
return answer
from collections import deque, defaultdict
class Robot:
def __init__(self, id, points, routes):
self.id = id
self.points = points
self.routes = deque(routes)
self.pos = points[self.routes.popleft() - 1]
self.target = points[self.routes[0] - 1]
def update(self):
if self.target is None:
self.pos = [-self.id, -self.id]
return
tx, ty = self.target
x, y = self.pos
dx = tx - x
dy = ty - y
if dx == 0 and dy == 0:
self.routes.popleft()
self.target = self.points[self.routes[0] - 1] if self.routes else None
return
if dx != 0:
x += 1 if dx > 0 else - 1
elif dy != 0:
y += 1 if dy > 0 else -1
self.pos = [x, y]
if x == tx and y == ty:
self.routes.popleft()
self.target = self.points[self.routes[0] - 1] if self.routes else None
def getPos(self):
return self.pos
def isArrived(self):
return self.target is None
def solution(points, routes):
answer = 0
robots = [Robot(i + 1, points, route) for i, route in enumerate(routes)]
while len(robots) > 1:
counts = defaultdict(int)
for robot in robots:
counts[tuple(robot.getPos())] += 1
answer += sum(1 for count in counts.values() if count > 1)
robots = [robot for robot in robots if not robot.isArrived()]
for robot in robots:
robot.update()
return answer
def solution(cap, n, deliveries, pickups):
answer = 0
'''
cap: 트럭에 담을 수 있는 상자 수
트럭으로 배달과 수거를 하는 최소 이동거리
가장 멀리있는 집부터, 배달, 수거 -> 그리디
1. 가장 큰 인덱스부터 검사하면서 cap만큼 빼기 -> 해당 인덱스의 deliveries와 pickups가 0이하가 될때까지
위에서 루프를 돈 횟수 * 2 * (i+1) 만큼 이동한거임
'''
#length_d = 0
#length_p = 0
while deliveries or pickups:
# while deliveries.count(0)==len(deliveries) and pickups.count(0)==len(pickups):
# for i in range(len(deliveries)-1,-1,-1):
# if deliveries[i] != 0:
# length_d = i+1
# break
# for j in range(len(pickups)-1,-1,-1):
# if pickups[j] != 0:
# length_p = j+1
# break
#마지막에서 0인부분은 다 pop해버리기
while deliveries and deliveries[-1]==0:
deliveries.pop()
while pickups and pickups[-1] == 0:
pickups.pop()
# 해당루프에서 이동거리 -> p와 d중 더 먼거리를 가야됨
answer += max(len(deliveries),len(pickups))*2
#한번 왔다갔다할때는 cap개수만큼 배달가능, cap개수만큼 수거가능
#따라서 while문돌면서 d_cap = cap, p_cap = cap만큼 배달, 수거하기
d_cap = cap
it = len(deliveries)-1
while d_cap != 0 and 0<=it<len(deliveries):
if deliveries[it] <= d_cap:
d_cap -= deliveries[it]
deliveries[it] = 0
else:
deliveries[it] -= d_cap
d_cap = 0
it -= 1
p_cap = cap
it = len(pickups) -1
while p_cap != 0 and 0<=it<len(pickups):
if pickups[it] <= p_cap:
p_cap -= pickups[it]
pickups[it] = 0
else:
pickups[it] -= p_cap
p_cap = 0
it -= 1
return answer