[Python 3] BOJ - 1581 "락스타 락동호"

 # 문제 링크

https://www.acmicpc.net/problem/1581

1581번: 락스타 락동호

 

 # 풀이

 개인적으로 이 문제의 핵심은 그래프 모델링이라고 생각한다.

<그림 1. 그래프 모델링>

 위 그림 1은 가능한 상태 전이를 그래프로 모델링한 것이다. 빠르게 끝나는 곡과 빠르게 시작하는 곡, 느리게 시작하는 곡과 느리게 시작하는 곡을 간선으로 이어준 형태이며 주의할 점은 FF, SS의 경우는 루프가 존재할 수 있다는 점이다. 따라서, (현재 곡의 종류, 이때까지 연주한 곡의 수, 연주한 FF의 수, 연주한 FS의 수, 연주한 SF의 수, 연주한 SS의 수)를 상태 공간으로 하는 BFS를 통해 최대로 연주할 수 있는 곡을 알 수 있다

 

 # 코드

import sys, collections

# go : kind에 따라 가능한 모든 경우를 탐색하여 최대 가능 공연곡의 수를 리턴하는 함수
def go(kind):
    q = collections.deque()
    # check : 현재 곡의 종류가 i, 이때까지 연주한 곡의 수가 j일 때 가능한지 아닌지 체크하는 상태 공간
    check = [[False] * (val + 1) for _ in range(4)]
    # 첫 곡은 항상 가능함
    check[kind][1] = True
    # 종류에 따라 초기값이 달라짐
    if kind == 0:
        q.append((kind, 1, 1, 0, 0, 0))
    elif kind == 1:
        q.append((kind, 1, 0, 1, 0, 0))
    elif kind == 2:
        q.append((kind, 1, 0, 0, 1, 0))
    else:
        q.append((kind, 1, 0, 0, 0, 1))
    while q:
        k, c, ff, fs, sf, ss = q.popleft()
        for i in adj[k]:
             # 더 연주할 수 있고 아직 한번도 가지 않았다면 탐색
            if c + 1 <= val:
                if not check[i][c + 1]:
                    if i == 0 and ff + 1 <= arr[0]:
                        check[i][c + 1] = True
                        q.append((i, c + 1, ff + 1, fs, sf, ss))
                    elif i == 1 and fs + 1 <= arr[1]:
                        check[i][c + 1] = True
                        q.append((i, c + 1, ff, fs + 1, sf, ss))
                    elif i == 2 and sf + 1 <= arr[2]:
                        check[i][c + 1] = True
                        q.append((i, c + 1, ff, fs, sf + 1, ss))
                    elif i == 3 and ss + 1 <= arr[3]:
                        check[i][c + 1] = True
                        q.append((i, c + 1, ff, fs, sf, ss + 1))
                        
    # 가능한 연주곡의 최대값 갱신
    res = 0
    for i in range(4):
        for j in range(val + 1):
            if check[i][j]:
                res = max(res, j)
    return res


arr = list(map(int, sys.stdin.readline().split()))
val = sum(arr)

# adj : 각 곡의 종류에 따라 갈 수 있는 다른 곡의 종류를 저장하는 인접 리스트
adj = [[0, 1], [2, 3], [0, 1], [2, 3]]
ans = 0

# 빠른 시작곡이 있다면 빠른 곡 먼저 연주해야 하므로
if arr[0] > 0:
    ans = max(ans, go(0))
if arr[1] > 0:
    ans = max(ans, go(1))
# 빠른 시작곡이 없다면 느린 시작곡을 연주할 수 있으므로
if arr[0] == 0 and arr[1] == 0:
    if arr[2] > 0:
        ans = max(ans, go(2))
    if arr[3] > 0:
        ans = max(ans, go(3))
# 정답 출력
print(ans)