[네이버 코테 준비] 알고리즘 스터디 D - 1

3. 광물캐기

처음에는 무조건 다이아몬드>철>돌 곡괭이 순으로 선택해서 해결하면 되지 않을까..? 라고 생각했다. 

그런데 생각해보면, 돌을 캐기 위해 다이아몬드 곡괭이를 쓰는 것은 낭비가 될 것이고,

다이아몬드를 캐기위해 돌 곡괭이를 쓰는 것은 큰 손실이 될 것이다. 

 

이 문제는 한 번 곡괭이를 선택하면 광물을 순서대로 5개씩 캐야 하므로, 

'5개씩 묶인 광물 청크를 어떤 곡괭이를 써야 피로도가 최적이 되는지를 선택' 하는 문제라고 볼 수 있다. 

 

1. 광물 배열을 5개씩 쪼개어 다이아몬드, 철, 돌 광물이 많은 순으로 정렬

2. 다이아몬드>철>돌 곡괭이 순으로 사용.

 

해당 풀이는 왠지 모르게 최종 제출 시 한 문제를 통과하지 못하고 있음. 일단 패스!

from collections import deque, Counter

mine = [[1, 1, 1],[5, 1, 1],[25, 5, 1]]
#다이아, 철, 돌 순으로 곡괭이를 선택하는 것이 좋음.

def sort_minerals(minerals):
    minerals = deque(minerals)
    five_chunk = []
    while minerals:
        chunk = []
        for i in range(5):
            try:
                chunk.append(minerals.popleft())   
            except: break
        five_chunk.append([chunk.count('diamond'), chunk.count('iron'), chunk.count('stone')])
        
    five_chunk = sorted(five_chunk, key= lambda x: (x[0], x[1], x[2]), reverse=True)
    return deque(five_chunk)

def drop_tool(picks):
    for idx, tool in enumerate(picks):
        if tool > 0 :
            picks[idx] -= 1
            return idx

def solution(picks, minerals):
    sorted_minerals = sort_minerals(minerals)
    cost = 0
    while sorted_minerals and sum(picks) > 0:
        tool = drop_tool(picks)
        five_chunk = sorted_minerals.popleft()
        cost += five_chunk[0]*mine[tool][0] #다이아몬드 피로도 계산
        cost += five_chunk[1]*mine[tool][1] #철 피로도 계산
        cost += five_chunk[2]*mine[tool][2] #돌 피로도 계산
    return cost

참고 코드 https://kcw0360.tistory.com/5

[programmers] Lv2 광물 캐기 - Python

탐욕 알고리즘에 해당한다고 해서 관련 지식을 찾아보았다.

순간 순간 최적의 해를 구함으로써 최종적으로 최적해를 구하는 방법.

https://nicola-ml.tistory.com/82?category=861276 

코딩테스트 이론: 그리디 알고리즘 (Greedy Algorithm)

 

4. 부대복귀

처음에는 각 부대원의 위치에서 각각 동일한 목적지까지 도달하는 최단 거리를 구하다보니 시간 초과가 났다.

from collections import deque 

def make_graph(n, roads):
    graph = {}
    for i in range(1, n+1):
        graph[i] = []
    for road in roads:
        key, value = road[0], road[1]
        graph[key].append(value)
        graph[value].append(key)
    return graph 
        
def solution(n, roads, sources, destination):
    graph = make_graph(n, roads)
    # print(graph)
    answer = []
    
    for source in sources:
        queue = deque([(source, 0)]) #start, step
        visited = [source]
        is_answer = False
        while queue:
            loc, step = queue.popleft()
            if loc == destination:
                answer.append(step)
                is_answer = True
                break
            else:
                visited.append(loc)
            for v in graph[loc]:
                if v not in visited:
                    visited.append(v)
                    queue.append((v, step+1))
            # print(visited, queue)
            
        if not is_answer: answer.append(-1)
            
    return answer

반대로, 동일한 목적지에서 모든 지역의 위치까지 도달하는 최단 거리를 구한다면?

from collections import deque 

def make_graph(n, roads):
    graph = {}
    for i in range(1, n+1):
        graph[i] = []
    for road in roads:
        key, value = road[0], road[1]
        graph[key].append(value)
        graph[value].append(key)
    return graph 
        
def solution(n, roads, sources, destination):
    graph = make_graph(n, roads)
    # print(graph)
    locations = [-1 for i in range(n+1)]
    locations[destination] = 0
    # print(locations)
    
    queue = deque([destination]) #start
    visited = set([destination])
    while queue:
        loc = queue.popleft()
        for v in graph[loc]:
            if v not in visited:
                visited.add(v)
                locations[v] = locations[loc]+1
                queue.append(v)
            # print(visited, queue, locations)

    # print(locations)
    return [locations[s] for s in sources]

참고 코드 https://velog.io/@dlrjs2360/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Python3-%EB%B6%80%EB%8C%80%EB%B3%B5%EA%B7%80

[ 프로그래머스 / Python3 ] 부대복귀