[백준 2572/Python] 보드게임

1. 문제 / 난이도 : Gold Ⅳ

www.acmicpc.net/problem/2572

2572번: 보드게임

---

2. 풀이 및 코드 설명

처음에는 가능한 모든 경우의 수를 다 해봐야 하나...? 라고 생각했지만 K의 최대가 10000이고, N의 최대가 1000이어서 모든 경우의 수를 돌면 10000의 1000제곱....빠르게 포기했다. 다른 방법을 생각해보았다.

 

그래서 그 다음 생각한 방법이 DP를 이용해 푸는 것! 다음과 같은 입력이 들어올 때로 예를 들면,

5
R G R B G
4 5
1 2 R
1 3 G
2 3 G
1 4 R
4 3 B

다섯번째 G 카드를 들고 있을 때 각각의 마을에서 얻는 점수를 계산해보면, DP 배열은 다음과 같다

색상 \ 마을	1	2	3	4
R
G
R
B
G	10	10	10	0

그 다음, 네번째 B 카드를 들고 있을 때 1번 마을의 경우를 살펴보면 => 1번 마을에서는 2, 3, 4번 마을로 갈 수 있으므로

2번 마을로 가는 경우 = DP[5][2] + 0 = 10 + 0 = 10

3번 마을로 가는 경우 = DP[5][3] + 0 = 10 + 0 = 10

4번 마을로 가는 경우 = DP[5][4] + 0 = 0 + 0 = 0

세가지 경우의 MAX값은 10이다.

(* 빨간색 숫자는 해당 마을로 움직일 때 얻는 점수, B카드를 들고 있을 때 1번에서 2번 마을로 가는 경우에는 R색의 길을 지나므로 점수를 얻기 때문에 0을 더해준다)

 

마찬가지로 네번째 B 카드를 들고 있을 때 4번 마을의 경우를 살펴보면 => 4번 마을에서는 1, 3번 마을로 갈 수 있으므로

1번 마을로 가는 경우 = DP[5][1] + 0 = 10 + 0 = 10

3번 마을로 가는 경우 = DP[5][3] + 10 = 10 + 10 = 20

두가지 경우의 MAX값은 20이다.

 

위와 같은 과정을 거쳐 DP배열은 전부 채우면, DP는 다음과 같은 형태가 된다.

색상 \ 마을	1	2	3	4
R	40	40	30	40
G	30	30	40	30
R	30	20	20	20
B	10	10	10	20
G	10	10	10	0

원하는 것은 1번 마을에서 첫번째 카드를 들고 있을 때 얻을 수 있는 점수의 최댓값이므로 DP[1][R]이 답이된다.

 

(1) 설정 및 초기화

# 보드 정보 저장
for _ in range(K):
    i, j, c = sys.stdin.readline().split()
    board[int(i)].append((int(j), c))
    board[int(j)].append((int(i), c))
# dp 배열 초기화
dp = [[0 for _ in range(M + 1)] for _ in range(N+1)]

board[i] : i에서 갈 수 있는 정점과, 그 때 지나는 길의 색이 튜플 형태로 저장되어 있음

 

(2) DP배열 채우기

for i in range(N-1, -1, -1): # 카드를 하나씩 돌면서
    current_card = cards[i] # 현재 카드
    for j in range(M, 0, -1): # 각 마을을 하나씩 돌면서
        temp = 0
        for k in board[j]: # 해당 마을에서 갈 수 있는 정점의 정보
            node = k[0] # 정점 번호
            vertex = k[1] # 길의 색
            temp = max(dp[i+1][node] + (10 if vertex == current_card else 0), temp) # 모든 경우의 최댓값
        dp[i][j] = temp

 

---

3. 전체 코드

import sys

N = int(input())
cards = sys.stdin.readline().split()
M, K = map(int, sys.stdin.readline().split())
board = [[] for _ in range(M + 1)]

for _ in range(K):
    i, j, c = sys.stdin.readline().split()
    board[int(i)].append((int(j), c))
    board[int(j)].append((int(i), c))

dp = [[0 for _ in range(M + 1)] for _ in range(N+1)]

for i in range(N-1, -1, -1):
    current_card = cards[i]
    for j in range(M, 0, -1):
        temp = 0
        for k in board[j]:
            node = k[0]
            vertex = k[1]
            temp = max(dp[i+1][node] + (10 if vertex == current_card else 0), temp)
        dp[i][j] = temp
print(dp[0][1])