[코딩테스트] 현대오토 2026-04-05 회고

1. 탐색 문제

""" N x M 크기의 격자판에 1부터 N x M까지의 숫자가 순서대로 적혀 있습니다. 
    당신은 1번 칸에서 출발하여 주어진 targets 리스트에 포함된 모든 숫자를 한 번씩 방문해야 합니다. 
    숫자를 방문하는 순서는 상관없으며, 이미 지나간 칸을 다시 지나가거나 이미 방문한 숫자를 다시 밟는 것도 허용됩니다. 
    격자판의 상하좌우로 한 칸 이동하는 데 거리가 1일 때, 모든 targets를 방문하고 멈추는 최단 거리를 구하세요.
    입력 예시: m=5, n=2, targets=[1, 5, 8]출력 예시: 6"""

from collections import deque

def solve(m, n, targets):
    # ---------------------------------------------------------
    # 1. 좌표 변환 (Preprocessing)
    # 1차원 숫자(노드 번호)를 2차원 격자상의 (r, c) 좌표로 변환합니다.
    # ---------------------------------------------------------
    target_pos = {}
    for num in targets:
        # 숫자가 1부터 시작하므로 인덱스 계산을 위해 1을 빼줍니다.
        # 예: m=5일 때 숫자 5는 인덱스 4 -> (4//5, 4%5) = (0, 4)
        r = (num - 1) // m
        c = (num - 1) % m
        target_pos[num] = (r, c)
    
    # ---------------------------------------------------------
    # 2. 두 지점 간 최단 거리 측정 함수 (BFS)
    # 지도를 직접 탐색하여 start_node에서 end_node까지의 최소 칸 수를 구합니다.
    # ---------------------------------------------------------
    def get_dist(start_node, end_node):
        sr, sc = target_pos[start_node] # 출발지 (행, 열)
        er, ec = target_pos[end_node]   # 목적지 (행, 열)
        
        # 큐 데이터 구성: (현재_행, 현재_열, 지금까지_이동_거리)
        queue = deque([(sr, sc, 0)])
        
        # 방문 체크: 특정 칸을 중복 방문하지 않기 위함 (해당 BFS 차수 내에서만 유효)
        visited = [[False] * m for _ in range(n)]
        visited[sr][sc] = True
        
        # 방향 벡터: 상, 하, 좌, 우
        dr = [-1, 1, 0, 0]
        dc = [0, 0, -1, 1]
        
        while queue:
            curr_r, curr_c, dist = queue.popleft()
            
            # 목적지 좌표에 도달한 경우 현재까지의 거리를 즉시 반환
            if curr_r == er and curr_c == ec:
                return dist
            
            # 4방향 탐색
            for i in range(4):
                nr, nc = curr_r + dr[i], curr_c + dc[i]
                
                # 격자 범위 내에 있고, 아직 방문하지 않은 칸이라면 큐에 추가
                if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc]:
                    visited[nr][nc] = True
                    queue.append((nr, nc, dist + 1))
        
        return float('inf') # 도달 불가능할 경우 (문제 조건상 발생 안 함)

    # ---------------------------------------------------------
    # 3. 거리 행렬 생성 (Distance Matrix)
    # 모든 타겟 노드들끼리의 거리를 미리 계산해둡니다. (이후 지도 탐색은 더 이상 필요 없음)
    # ---------------------------------------------------------
    dist_matrix = {u: {v: 0 for v in targets} for u in targets}
    for u in targets:
        for v in targets:
            if u != v:
                # u에서 v로 가는 최단 거리를 BFS로 측정하여 저장
                dist_matrix[u][v] = get_dist(u, v)

    # ---------------------------------------------------------
    # 4. 최적 경로 탐색 (DFS / Backtracking)
    # 어떤 순서로 방문해야 전체 합계가 최소가 될지 모든 경우의 수를 따집니다.
    # ---------------------------------------------------------
    self_min_dist = float('inf') # 정답을 저장할 변수 (최솟값을 찾기 위해 무한대로 초기화)
    
    # 방문 여부 체크: 'targets' 내의 노드 방문 여부
    is_visited = {node: False for node in targets}
    is_visited[1] = True # 시작점인 1번 노드는 이미 방문한 상태로 시작
    
    def find_path(curr, count, total_d):
        """
        curr: 현재 위치한 노드 번호
        count: 지금까지 방문 완료한 노드의 개수
        total_d: 지금까지 누적된 이동 거리
        """
        nonlocal self_min_dist
        
        # [가지치기] 현재 거리가 이미 찾은 최솟값보다 크다면 더 이상 탐색할 가치가 없음
        if total_d >= self_min_dist: 
            return
            
        # [기저 사례] 모든 타겟 노드를 다 방문했다면 최솟값 갱신 후 종료
        if count == len(targets):
            self_min_dist = min(self_min_dist, total_d)
            return
            
        # 다음에 방문할 노드를 하나씩 선택
        for next_node in targets:
            if not is_visited[next_node]:
                is_visited[next_node] = True # 방문 표시
                # 다음 노드로 이동 (누적 거리 합산)
                find_path(next_node, count + 1, total_d + dist_matrix[curr][next_node])
                is_visited[next_node] = False # 백트래킹: 돌아와서 방문 표시 해제

    # 재귀 시작: 1번 노드에서, 방문 수 1개, 총 거리 0
    find_path(1, 1, 0)
    
    return self_min_dist

# 테스트 케이스 실행
print(solve(5, 2, [1, 5, 8])) # 예상 결과: 6

 

---

2. 적 무찌르기

"""당신은 적들을 차례로 무찌르는 게임을 하고 있습니다. 각 적은 정수 값의 체력을 가지고 있으며, 이 값은 양수(체력 회복)일 수도 있고 음수(체력 감소)일 수도 있습니다.
    1. 당신의 초기 체력은 자유롭게 설정할 수 있지만, 게임 도중이나 적을 무찌른 직후에 체력이 0 이하가 되면 패배합니다. (최소 1 유지)
    2. 적을 무찌르면 (나의 체력 + 적의 체력)이 나의 새로운 체력이 됩니다.
    3. 주어진 적들 중 k명을 선택하여 무찌를 때, 필요한 초기 체력의 최솟값을 구해야 합니다. k명의 적을 선택하는 순서와 조합은 자유롭습니다.
    4. 1명부터 전체 인원 N명까지 무찌를 때 각각 필요한 최소 초기 체력을 리스트에 담아 반환하세요.
    
    입력 예시: enemies = [-2, 3, 7, 12]
    출력 예시: [1, 1, 1, 1] (만약 모든 적이 음수라면 [3, 8, 18...] 등의 형태)"""

import heapq

def solve(enemies):
    # 1. 모든 적을 최대 힙에 담습니다. (가장 큰 체력부터 꺼내기 위해 마이너스 부호 사용)
    # 파이썬 heapq는 최소 힙이므로 -를 붙여 최대 힙처럼 동작하게 합니다.
    max_heap = []
    for e in enemies:
        heapq.heappush(max_heap, -e)
    
    answer = []
    current_selected = []
    
    # 2. k명을 하나씩 늘려가며 선택
    for k in range(1, len(enemies) + 1):
        # 이번 단계에서 가장 유리한 적 한 명을 힙에서 꺼내 현재 조합에 추가
        best_enemy = -heapq.heappop(max_heap)
        current_selected.append(best_enemy)
        
        # 3. 현재 선택된 k명의 적들을 '가장 유리한 순서'로 정렬 (내림차순)
        # 힙에서 꺼낸 순서대로 이미 정렬되어 있으므로, 
        # current_selected는 항상 내림차순이 유지됩니다.
        
        current_sum = 0
        min_prefix_sum = 0
        
        # 선택된 적들을 순차적으로 무찌르며 최저점 찾기
        for e_hp in current_selected:
            current_sum += e_hp
            if current_sum < min_prefix_sum:
                min_prefix_sum = current_sum
        
        # 최소 시작 체력 계산 (1 - 최저점)
        required_hp = max(1, 1 - min_prefix_sum)
        answer.append(required_hp)
        
    return answer

# 테스트 케이스
print(solve([-2, -5, -10])) # [3, 8, 18]
print(solve([-2, 3, 7, 12])) # [1, 1, 1, 1]