글 읽기 - 테케 6 질문 (정리있음)

sminhyuck 4년 전 0

예제6 값이 왜 계속 13이 나오는지 모르겠어요..

115번째에 x < tempC로 동일한 거리면 가장 왼쪽값을 가지게 했는데

이걸 반대로 하면 14가 나오긴 하는데 제출하면 틀렸다고 뜨구요..

왜 그런지 조언좀 부탁드리겠습니다.

일 떄, 궁수를 0, 2, 4 선택하면

1) (0,0), (0,2), (0,4) -> 3

2) (1,0), (0,1), (0,3) -> 3

3) (0,1), (0,1), (1,4) -> 2

4) (1,0), (1,4), (1,4) -> 2

5) (0,1), (0,1), (0,4) -> 2

6) (0,2) -> 1

이렇게 13인데, 어떻게 14가 나오는지 설명좀 부탁드리겠습니다!

#include <iostream>
#include <queue>
#define ENEMY 1
#define EMPTY 0
using namespace std;
struct pos {
	int R, C;
};
queue<pos> Q;
int MAP[16][16], back[16][16];
int ARCHER[3]; // ARCHER 가 위치하는 행은 항상 0, 배열의 값은 아처의 열위치를 나타냄
int N, M, D;	// 행, 열, 거리
int ANSWER;

void init();
void DFS(int s, int t);
void process();
void find(int c);

void print() {
	cout << endl;
	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= M; x++)
			cout << MAP[y][x] << " ";
		cout << endl;
	}
}

int main() {
	init();
	DFS(1, 0);
	cout << ANSWER << endl;
}

void init() {
	ANSWER = 0;
	cin >> N >> M >> D;
	for (int y = 1; y <= N; y++)
		for (int x = 1; x <= M; x++) {
			cin >> MAP[y][x];
			back[y][x] = MAP[y][x];
		}
}

void DFS(int s, int t) {
	if (t == 3) {
		process();

		for (int y = 1; y <= N; y++)
			for (int x = 1; x <= M; x++)
				MAP[y][x] = back[y][x];
		return;
	}

	for (int i = s; i <= M; i++) {
		ARCHER[t] = i;
		DFS(i + 1, t + 1);
	}
}

void process() {
	int point = 0;
	/*
	cout << "ARCHER: ";
	for (int i = 0; i < 3; i++) {
		cout << ARCHER[i]<< " ";
	}
	cout << endl;
	*/

	for (int t = 0; t < N; t++) {
		//print();
		
		for (int i = 0; i < 3; i++) 
			find(ARCHER[i]);
			
		// 3아쳐가 공격할 대상 정해짐, 제거 동작
		while (!Q.empty()) {
			int r = Q.front().R;
			int c = Q.front().C;
			Q.pop();
			//cout << "(" << r << "," << c << ") ";
			if (MAP[r][c] == ENEMY) {
				point++; MAP[r][c] = EMPTY; 
				
			}
		}
		//cout << endl;
		for(int y = 1; y < N-t; y++)
			for (int x = 1; x <= M; x++) {
				MAP[y][x] = MAP[y + 1][x];
				MAP[y + 1][x] = EMPTY;
			}
				
			
	}
	//cout << "POINT: " << point << endl;
	if (point > ANSWER) ANSWER = point;
}

// 아쳐가 공격할 적 찾아서 Q에 저장
void find(int c) {
	int min = D + 1;
	int tempR, tempC; // 행 열
	for (int y = 1; y <= D; y++) {
		for (int x = c - (D - y); x <= c + (D - y); x++) {
			int dis = abs(x - c) + abs(y - 0);
			
			if (x >= 1 && x <= N) {
				
				if (dis < min && MAP[y][x] == ENEMY) {
					min = dis; tempR = y; tempC = x;
				}
				else if (dis == min && MAP[y][x] == ENEMY) {
					if (x < tempC) {
						tempR = y; tempC = x;
					}
				}
			}
		}
	}
	if (min != D + 1) Q.push({ tempR, tempC });
}

djm03178 4년 전 1

"격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다."

"적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다."

두 번이나 '아래'라고 적혀있는데, 코드와 설명하신 것을 보니 둘 다 '위'로 하고 있습니다.

sminhyuck 4년 전 0

감사합니다! 아래로 이동부분을 제가 착각했네요!

그 부분 고쳐서 진행하니 테스트케이스와 질문 게시판에 있는 테스트케이스는 통과했습니다.

그런데 틀렸습니다가 뜨는걸 보니 예외 케이스가 발생하나 봅니다.

혹시 예외 케이스도 조언 해 주실수있나요?

코드 첨부합니다.

#include <iostream>
#include <queue>
#define ENEMY 1
#define EMPTY 0
using namespace std;
struct pos {
	int R, C;
};
queue<pos> Q;
int MAP[15][15], back[15][15];
int ARCHER[3]; // ARCHER 가 위치하는 행은 항상 0, 배열의 값은 아처의 열위치를 나타냄
int N, M, D;	// 행, 열, 거리
int ANSWER;

void init();
void DFS(int s, int t);
void process();
void find(int c);

int main() {
	init();
	DFS(0, 0);
	cout << ANSWER << endl;
}

void init() {
	ANSWER = 0;
	cin >> N >> M >> D;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++) {
			cin >> MAP[y][x];
			back[y][x] = MAP[y][x];
		}
}

void DFS(int s, int t) {
	if (t == 3) {
		process(); // 점수 계산
		
		// MAP 복원
		for (int y = 0; y < N; y++)
			for (int x = 0; x < M; x++)
				MAP[y][x] = back[y][x];
		return;
	}
	// ARCHER 위치선택
	for (int i = s; i < M; i++) {
		ARCHER[t] = i;
		DFS(i + 1, t + 1);
	}
}
// 점수 계산
void process() {
	int point = 0;
	for (int t = 0; t < N; t++) { // 최대 N회 만큼 동작
		for (int i = 0; i < 3; i++) 
			find(ARCHER[i]);
			
		// 3아쳐가 공격할 대상 정해짐, 제거 동작, 점수계산
		while (!Q.empty()) {
			int r = Q.front().R;
			int c = Q.front().C;
			Q.pop();
			if (MAP[r][c] == ENEMY) {	point++; MAP[r][c] = EMPTY; }
		}
		
		// 적들 아래로 이동
		for(int y = N-1; y >0+t; y--) // t만큼 위에 라인은 없어짐
			for (int x = 0; x < M; x++) {
				MAP[y][x] = MAP[y - 1][x];
				MAP[y - 1][x] = EMPTY;
			}
	}
	if (point > ANSWER) ANSWER = point; 
}

// 아쳐가 공격할 적 찾아서 Q에 저장
void find(int c) {
	int min = D + 1;
	int tempR, tempC; // 행 열
	for (int y = N-1; y > N-1-D; y--) // y축 D 만큼 위까지 탐색
		for (int x = c - D + (N - y); x <= c + D - (N - y); x++) { // x축 y반영해서 탐색
			int dis = abs(x - c) + abs(y - N);
			if (x >= 0 && x < N) { // MAP 범위 안에서만 동작
				if (dis < min && MAP[y][x] == ENEMY) { min = dis; tempR = y; tempC = x; } // 더 가까운 거리에 있는 적일때, 그 적의 위치 저장
				else if (dis == min && MAP[y][x] == ENEMY) { // 같은 거리에 있을때, 더 왼쪽에 있는 적 선택
					if (x < tempC) { tempR = y; tempC = x; }
				}
			}
		}
		
	if (min != D + 1) Q.push({ tempR, tempC }); // 제거할 적 선택
}

djm03178 4년 전 1

행의 수는 N이고 열의 수는 M인데 find 함수를 보면 M을 안 쓰고 N으로만 판별하고 있습니다.

sminhyuck 4년 전 0

정말 감사합니다!! 정말 작은 부분이라 찾기 힘들었는데 바로 잡아주셨네요!!

말씀하신 부분 수정하니 통과했습니다!

즐거운 주말 되세요! 감사합니다!

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

문제

문제

출처

ICPC

테케 6 질문 (정리있음)

sminhyuck 4년 전 0

djm03178 4년 전 1

sminhyuck 4년 전 0

djm03178 4년 전 1

sminhyuck 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말