글 읽기 - 무엇이 틀렸을까요... 주석 있습니다..

dmzld 3년 전 0

원 그리면서 도는 루트 0

루트 0에서

10에서 분기되는 루트 1

20에서 분기되는 루트 2

30에서 분기되는 루트3

으로 설계해서 dfs로 최대값을 찾아냅니다.

안되는 예제가 있는데 어느 부분이 틀렸을까요 ㅠ

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

int num[10];
int map[4][30] = { // [route][score for pos]
	{ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, },
	{ 0, 2, 4, 6, 8, 10, 13, 16, 19, 25, 30, 35, 40, },
	{ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 25, 30, 35, 40, },
	{ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 28, 27, 26, 25, 30, 35, 40, }
};
bool check[4][30] = { false, };

struct State{
	int route = 0;
	int pos = 0;
	bool arrive = false;
	int score = 0;
};
State horse[4];

int ans = 0;

void routeUpdate(int i, int n){
	if (horse[i].route == 0){
		if (map[horse[i].route][horse[i].pos] == 10) // pos == 5
			horse[i].route = 1;
		else if (map[horse[i].route][horse[i].pos] == 20) // pos == 10
			horse[i].route = 2;
		else if (map[horse[i].route][horse[i].pos] == 30) // pos == 15
			horse[i].route = 3;
	}
}

void solution(int n){ // dfs

	if (n >= 10){ // game over
		ans = max(ans, horse[0].score + horse[1].score + horse[2].score + horse[3].score);
		return;
	}

	for (int i = 0; i < 4; i++){
		if (!horse[i].arrive && !check[horse[i].route][horse[i].pos + num[n]]){
			// save state
			State tmp = horse[i];

			// update current data
			check[horse[i].route][horse[i].pos] = false;
			horse[i].pos += num[n];
			routeUpdate(i, n);

			// check whether arriving or not
			if (map[horse[i].route][horse[i].pos] == 0){
				horse[i].arrive = true;
			}
			else{
				check[horse[i].route][horse[i].pos] = true;
				horse[i].score += map[horse[i].route][horse[i].pos];
			}

			// next step
			solution(n + 1);

			// rollback
			check[horse[i].route][horse[i].pos] = false;
			horse[i] = tmp;
			check[horse[i].route][horse[i].pos] = true;
		}
	}
}

int main(){

	ios::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 0; i < 10; i++)
		cin >> num[i];

	solution(0);

	cout << ans;

	return 0;
}

nietzhan 3년 전 1

일단 눈에 보이는 두 가지만 말씀드리겠습니다.

1. routeUpdate 함수에서 horse[i].pos = 0; 도 넣어주셔야 합니다.

2. 50번 줄에서 check 배열로 현재 말이 이동하려고 하는 칸에 다른 말이 있는지 검사하고 있는데, 저 코드로는 같은 루트 상의 말만 검사할 수 있습니다.
가령 horse[1].route = 0, horse[1].pos = 2 이고 현재 턴의 num[n] = 3인데, horse[2].route = 1, horse[2].pos = 0 이라면 충돌이 나서 이동을 하지 않아야 하는게 맞는데 현재 코드로는 이 부분을 체크하지 못합니다.

nietzhan 3년 전 0

**2번에서 말씀드린 예시는, 1번 말을 이동하려고 했을 경우를 가정한 것입니다.

dmzld 3년 전 1

답변 감사합니다.

그런데 제가 설계한 루트는 분기가 되었다고해서 pos가 0으로 갱신되는게 아니고

모든 루트가 시작부터 도착까지 모든 pos를 포함하고 있습니다

즉 루트0의 pos 1과 루트 1의 pos 1은 score가 2인 칸으로 같지만

루트 0의 pos 6은 score가 12이고, 루트 1의 pos 6은 10에서 분기되어 13이되어 다른거죠.

그래서 updateRoute에서는 루트가 몇인지만 갱신해주면 되는 것으로 짰습니다.

제가 답변자님의 말씀을 잘 이해하지 못한 것일 수도 있습니다..

dmzld 3년 전 0

1. check 할 때에 route 변화 처리와 2.예외처리를 안해줘서 틀린 것이었네요

혹시 다른분들 도움이 될까 설명해드리면

1. 50번째 줄에서 움직였을 때 위치가 분기점이라면 route를 갱신한 상태를 가지고 해당 route의 칸에 다른 말이 있는지 검증해야합니다.

2. 루트를 나누어 설계했지만 루트끼리 겹치는 칸이 있습니다.

map[route][pos]라 할 때

1) map[1][9 ~ 11] == map[2][13 ~ 15] == map[3][19 ~ 21]
2) map[0][20] == map[1][12] == map[2][16] == map[3][22]

이기 때문에 조건에 부합하는 케이스라면 추가적으로 다른 루트들의 칸을 체크해주어야 합니다.

통과 코드도 남깁니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

int num[10];
int map[4][30] = { // [route][score for pos]
	{ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, },
	{ 0, 2, 4, 6, 8, 10, 13, 16, 19, 25, 30, 35, 40, }, // branch from 10
	{ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 25, 30, 35, 40, }, // branch from 20
	{ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 28, 27, 26, 25, 30, 35, 40, } // branch from 30
};

bool check[4][30] = { false, };

struct State{
	int route = 0;
	int pos = 0;
	bool arrive = false;
	int score = 0;
};
State horse[4];

int ans = 0;


int getNextRoute(int i, int n){
	if (horse[i].route == 0){ // branch can be occured when route is 0
		if (map[horse[i].route][horse[i].pos + num[n]] == 10)
			return 1;
		else if (map[horse[i].route][horse[i].pos + num[n]] == 20)
			return 2;
		else if (map[horse[i].route][horse[i].pos + num[n]] == 30)
			return 3;
	}
	
	return horse[i].route; // no change then return own route
}

bool checkDup(int i, int n){
	// next position
	int r = getNextRoute(i, n);
	int pos = horse[i].pos + num[n];

	// normal case
	if (check[r][pos]) return true;

	// special case : different route but duplicated space
	// map[1][9 ~ 11] == map[2][13 ~ 15] == map[3][19 ~ 21]
	// map[0][20] == map[1][12] == map[2][16] == map[3][22]
	if (r == 0 && pos == 20){
		if (check[1][12] || check[2][16] || check[3][22]) return true;
	}
	else if (r == 1 && pos >= 9 && pos <= 12){
		if (check[2][pos + 4] || check[3][pos + 10] || (pos == 12 && check[0][20])) return true;
	}
	else if (r == 2 && pos >= 13 && pos <= 16){
		if (check[1][pos - 4] || check[3][pos + 6] || (pos == 16 && check[0][20])) return true;
	}
	else if (r == 3 && pos >= 19 && pos <= 22){
		if (check[1][pos - 10] || check[2][pos - 6] || (pos == 22 && check[0][20])) return true;
	}

	return false; // not dup
}

void solution(int n){ // dfs

	if (n >= 10){ // game over
		ans = max(ans, horse[0].score + horse[1].score + horse[2].score + horse[3].score);
		return;
	}

	for (int i = 0; i < 4; i++){
		if (!horse[i].arrive && !checkDup(i, n)){ // not arrive && there is no horse in next space
			// save state
			State tmp = horse[i];

			// update data
			check[horse[i].route][horse[i].pos] = false;
			horse[i].route = getNextRoute(i, n); 
			horse[i].pos += num[n];

			// check whether arriving or not
			if (map[horse[i].route][horse[i].pos] == 0){
				horse[i].arrive = true;
			}
			else{
				check[horse[i].route][horse[i].pos] = true;
				horse[i].score += map[horse[i].route][horse[i].pos];
			}

			// next step
			solution(n + 1);

			// rollback
			check[horse[i].route][horse[i].pos] = false;
			horse[i] = tmp;
			check[horse[i].route][horse[i].pos] = true;
		}
	}
}

int main(){

	ios::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 0; i < 10; i++)
		cin >> num[i];

	solution(0);

	cout << ans;

	return 0;
}

nietzhan 3년 전 0

잘 해결하셨군요.. 워낙 코드를 읽기편하게 작성하셔서 몇자 적어봤었는데 행여 방해가 된건 아니었을지 죄송합니다. 건승하세요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

무엇이 틀렸을까요... 주석 있습니다..

dmzld 3년 전 0

nietzhan 3년 전 1

nietzhan 3년 전 0

dmzld 3년 전 1

dmzld 3년 전 0

nietzhan 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말