1/12 Coding Test

✅ Coding Test

🎈 1516 게임개발

게임 개발에 있어 핵심적인 부분은 개발이 끝난 상태고 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아있다.
게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있고 모드 건물을 짓는데 걸리는 최소 시간을 이용해 근사하기로 했다. 편의상 자원은 무한히 많고 건물을 짓는 명령을 내리기 전까지 시간이 걸리지 않는다고 하자.

첫 줄에 건물의 종류 수 N이 주어지고 다음 N줄만큼 각 건물을 짓는데 걸리는 시간, 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물 번호는 1부터 N이고 각 줄은 -1로 끝이 난다. 결과적으로 N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력하는 문제

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
# 그래프 정보 입력 (i, j) : j번째 건물을 짓기 전 i번째 건물이 지어져야 함.
graph = [[] for _ in range(n+1)]
# 각 건물 짓기 전 필요한 건물 수
indegree = [0]*(n+1)
# 건물 짓는데 드는 시간
dp = [0] * (n+1)

for i in range(1, n+1):
    info = list(map(int, input().split()))[:-1]
    dp[i] = info[0]
    before = info[1:]
    for j in before:
        graph[j].append(i)
        indegree[i] += 1
answer = [0] * (n+1)
queue = deque()
for i in range(1, n+1):
    if indegree[i] == 0:
        queue.append(i)
while queue:
    x = queue.popleft()
    answer[x] += dp[x]
    for i in graph[x]:
        indegree[i] -= 1
        answer[i] = max(answer[x], answer[i])
        if indegree[i] == 0:
            queue.append(i)
for i in range(1, n+1):
    print(answer[i])

< 해설 >
위상정렬이기에 다음에 다시 풀이해보기.
간단히 요약하면 위상정렬로 그래프 내 진입차수가 0이면 큐에 넣어서 다음 노드를 탐색하며 시간을 더해주는 방식. 주요 변수는 다음과 같다.

• graph : (i, j)로 이루어져 있다면, j번째 건물을 짓기 전에 i번째 건물이 완성되어야 한다.
• indegree : i번째 건물을 짓는데 필요한 건물의 개수
• dp : 건물 짓는데 드는 시간 (base)
• answer : 최종적으로 건물 짓는데 드는 시간

🎈 1520 내리막길

지도는 직사각형 모양으로 되어 있고 각 칸은 아래 그림처럼 해당 지점의 높이가 쓰여져 있다.

경로 이동 시 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 이동하고자 하는데 항상 내리막길로만 이동할 수 있는 경로의 개수를 구하는 문제이다.

입력값으로 첫 줄에는 세로, 가로 크기인 M,N이 주어지고 M줄에 거쳐 한 줄에 N개씩 각 지점의 높이가 주어진다.
최종적으로 이동 가능한 경로 수를 출력하는 문제

import sys, heapq
input = sys.stdin.readline

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]

def search():
    heap = [(-graph[0][0], 0, 0)]
    visited = [[0]*n for _ in range(m)]
    visited[0][0] = 1
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while heap:
        height, x, y = heapq.heappop(heap)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<m and 0<=ny<n and graph[nx][ny] < graph[x][y]:
                if not visited[nx][ny]:
                    heapq.heappush(heap, (-graph[nx][ny], nx, ny))
                visited[nx][ny] += visited[x][y]
    return visited[m-1][n-1]
print(search())

< 해설 >

DP에 우선순위큐를 결합해 해결하고자 했다.
기본적인 heapq의 경우 최소 힙을 기반으로 하기 때문에 -value를 활용하여 최대 힙으로 변환해 문제를 해결했다.
로직은 다음과 같다.
1. 힙에 현재 높이, 위치를 넣어주고 현 위치를 방문 처리 한다.
2. 힙이 비어있지 않는 동안, 4방향 탐색을 진행하되 주어진 범위를 만족하며 다음 위치의 높이가 더 낮고 방문한 적이 없어야 힙에 넣어준다. (힙에 넣을 때도 -height로 처리해 높이가 낮아지도록 처리)
3. visited[x][y]는 x,y까지 갈 수 있는 방법의 경우의 수를 의미하므로 n-1, m-1 칸의 visited 값을 리턴한다.