[Python] 백준 2572 보드게임

문제 링크 : https://www.acmicpc.net/problem/2572

2572번: 보드게임

1. 접근 방법

처음에는 문제를 잘못 읽어 너무 많은 경우의 수가 아닌가 하는 생각을 했다.

카드를 순서대로 뽑으며 각 이동하는 모든 경우의 수를 계산해야 되고, 최대 탐색 마을의 수와 카드의 수가 적지 않아 DP와 DFS 중 고민했다. 그런데 길의 수가 마을에 비해 너무 많아 DP가 더 적절할 것 같아 DP로 접근했지만, 쉽지는 않았다.

 

 

2. 풀이 코드

🖥python

import sys
input = sys.stdin.readline

n = int(input())
cards = list(input().strip().split())

m, k = map(int, input().split())
cities = [[] for _ in range(m + 1)]
for _ in range(k):
    a, b, c = input().strip().split()
    a, b = int(a), int(b)
    cities[a].append((b, c))
    cities[b].append((a, c))

# i번째 카드를 냈을 때 j번 마을에 있다면
dp = [[-1] * (m + 1) for _ in range(n + 1)]
dp[0][1] = 0
for i in range(n):
    # 이번 카드의 생상
    color = cards[i]
    # 1번 마을부터 m번 마을까지
    for j in range(1, m + 1):
        # 해당 마을까지 도착했을 때
        cost = dp[i][j]
        if cost >= 0:
            # 해당 마을에서 연결된 마을로 이동 탐색
            for k, c in cities[j]:
                # j >> k 비용과 기존 k마을까지 비용 비교
                if color == c and dp[i + 1][k] < cost + 1:
                    dp[i + 1][k] = cost + 1
                elif color != c and dp[i + 1][k] < cost:
                    dp[i + 1][k] = cost

if max(dp[-1]) == -1:
    print(0)
else:
    print(max(dp[-1]) * 10)

📕풀이과정

DP배열을 1차원으로 시도하려 했지만, 몇 번째 카드에서 각 마을에 도착했는지가 다시 영향을 미치게 되어 2차원 배열을 선택해야 했다.

이 외에는 각 순서의 카드를 선택하고, 해당 순번에 마을에 도착했다면, 해당 마을에서 연결된 마을을 모두 탐색한다. 여기서 두 가지로 나누어 시행하는데, 해당 도로의 색이 카드의 색과 같다면 점수를 추가하여, 아니라면 해당 점수로 최대 점수인지 비교하여 최신화한다.

 

 

3. 생각 정리

python으로 통과한 코드가 없고, 모두 시간초과였다. 조금 더 빠르게, 효율적으로 해결할 수 있지 않을까 라는 생각도 하지만, 아쉬운 건 아쉬운 대로 남겨두고, 우선은 문제를 잘 풀어가는데 집중하는 게 맞는 것 같다.

시간을 줄이는 부분을 생각해본다면, 탐색에서 줄이는 방법이 있어야 할 것 같은데, 딱히 떠오르지 않아 아쉬운 생각도 남는다.