✅ 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 값을 리턴한다.
