보드 게임

문제

다음 보드 게임은 N장의 카드를 갖고 시작한다.각각의 카드 앞면에는 1번부터 N번까지 번호가 순서대로 적혀 있고, 뒷면에는 빨간색(R), 녹색(G), 파란색(B) 중 하나의 색깔이 칠해져 있다.

항상 1번 마을로부터 시작하여 길이 연결되어 있는 이웃 마을로 이동해 가는데 한 번 이동할 때마다 갖고 있는 카드를 번호 순서대로 한 장씩 내야 한다. 각 길은 빨간색(R), 녹색(G), 파란색(B) 중 하나의 색깔이 칠해져 있는데 만약 내놓은 카드의 색깔과 길의 색깔이 일치하면 10점의 점수를 얻는다.

예를 들어 N이 5이고 1번부터 5번까지의 카드 색깔이 R, G, R, B, G이라고 하자. 지도가 <그림 1>과 같이 주어졌다고 할 때,

1번 마을에서 시작하여 2번 마을로 가면 길의 색깔과 1번 카드의 색깔이 R로 일치하므로 10점을 받게 된다. 다음 3번 마을로 가면 마찬가지로 길의 색깔과 2번 카드의 색깔이 G로 일치하므로 10점을 추가로 받게 된다. 이어 1번, 2번, 3번 마을로 이동하면 총 30점을 받는다. 하지만 1번 마을에서 시작하여 2번 마을을 거쳐 3번, 4번, 3번, 2번 마을로 이동하면 총 40점을 받게 된다.

갖고 있는 카드의 정보와 지도가 주어질 때 받을 수 있는 최대 점수를 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 카드의 수 N이 주어진다.

둘째 줄에 N장의 카드의 색깔이 번호 순서대로 빈칸을 사이에 두고 주어진다.

셋째 줄에는 마을의 수 M과 길의 수 K가 빈칸을 사이에 두고 주어진다.

이어 K개의 줄에 길의 정보가 주어진다. 길의 정보는 양 끝 마을의 번호를 나타내는 서로 다른 두 개의 자연수와 길의 색깔이 빈칸을 사이에 두고 주어진다. 두 마을을 잇는 길은 최대 1개이다. N은 1000이하의 자연수, M은 500이하의 자연수, K는 10000이하의 자연수이다. 카드의 색깔과 길의 색깔은 R, G, B중 하나이다.

---

출력

첫째 줄에 보드 게임에서 받을 수 있는 최대 점수를 출력한다.

---

힌트

예제 입력

5

R G R B G

4 5

1 2 R

1 3 G

2 3 G

1 4 R

4 3 B

예제 출력

40

---

#include <iostream> #include <queue> #include <algorithm> #include <limits.h> #include <vector> //BoardGame ------------------- void input(); void BoardGame(); //BoardGame ------------------- int main(int argc, char** argv) { BoardGame(); return 0; } //BoardGame ------------------- struct Town{ int number; int next; //인접 마을 번호 char color; //색깔 }; struct VisitTown{ int number; int count; }; int N, M, K; //카드수, 마을수(최대500), 길의 수 char card[1001]; //1000 std::vector<Town> townVector[501]; //마을 int D[1001][501]; void input(){ std::cin>>N; for(int i=1; i<=N; i++){ std::cin >> card[i]; } std::cin >> M >> K; int number, next; char color; for(int i=0; i<K; i++){ std::cin >> number >> next >> color; Town town1 = {number, next, color}; Town town2 = {next, number, color}; townVector[number].push_back(town1); townVector[next].push_back(town2); } } void BoardGame(){ input(); for(int i=0; i<=N; i++){ for(int j=0; j<=M; j++){ D[i][j] = -1; } } std::queue<VisitTown> visitTownQueue; VisitTown visitTown = {1, 1}; visitTownQueue.push(visitTown); D[1][1] = 0; int max = 0; while(!visitTownQueue.empty()){ //마을 방문 VisitTown curTown = visitTownQueue.front(); visitTownQueue.pop(); //현재 마을 번호 int townNumber = curTown.number; //나의 카드 번호(마을들른횟수) int count = curTown.count; //현재 카드 색깔 char cardColor = card[count]; //현재까지 글자색깔 최대 유사도 int curDegree = D[count][townNumber]; //인접 마을 방문 예약 std::vector<Town> townInfo = townVector[townNumber]; for(int j=0; j<townInfo.size(); j++){ Town nextTown = townInfo[j]; char pathColor = nextTown.color; //인접마을까지 가는 길의 색깔 int nextNumber = nextTown.next; // 인접마을의 번호 //다음유사도확인 //내가 가진 카드 색깔과 길의 색깔이 같으면 유사도 증가 int nextDegree = curDegree; if(pathColor == cardColor){ nextDegree += 10; } if(D[count+1][nextNumber]==-1){ //방문한 적 없음 D[count+1][nextNumber] = nextDegree; //새롭게 갱신 if(count<N){ //추가 방문이 가능할 경우 //다음 방문을 예약 VisitTown newVisitTown = {nextNumber, count+1}; visitTownQueue.push(newVisitTown); } }else{ //기존에 여기를 동일 카드로(동일한 횟수만에) 방문했을 때 최대유사도와 비교 if(nextDegree > D[count+1][nextNumber] ){ D[count+1][nextNumber] = nextDegree; //새롭게 갱신 } } if(max < nextDegree){ max = nextDegree; } } } printf("%d", max); }