글 읽기 - 예제는 다 맞는데 시작하자마자 틀렸습니다 뜹니다ㅜㅜ

jjparson 5년 전 0

예제는 다 맞는데 시작하자마자 틀렸습니다 뜹니다.

질문방에 있는 반례도 넣어봤는데 맞게 뜨구요ㅠㅠ

이틀을 고민해봤는데도

어디가 틀린건지 답이 안 나옵니다ㅠㅠ

도와주세요ㅠ.ㅠ

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct Pos {
	int r, c, v;
};

#define pi pair<int, int>
#define N 16
#define M 16
#define K 3

int map[N][M];
int arr[M];
vector<pi> killPos;
int n, m, d, sum, MAX = 0;

int dr[3] = { 0, -1, 0 };
int dc[3] = { -1, 0, 1 };

int check(int r, int c) { // 각각의 궁수가 죽일 적의 위치 찾기
	bool vst[N][M] = { false, };
	queue<Pos> q;

	q.push({ r, c, 1 });
	vst[r][c] = true;

	while (!q.empty()) {
		Pos top = q.front();
		q.pop();

		int nv = top.v + 1;
		if (nv > d) continue; //d를 벗어나는 곳은 탐색하지 않음

		for (int i = 0; i < 3; i++) {
			int nr = top.r + dr[i];
			int nc = top.c + dc[i];
			
			if (nr < 0 || nc < 0 || nc >= m) continue;
			if (vst[nr][nc]) continue;

			if (map[nr][nc] == 2) return 0; //앞의 궁수가 이미 죽인 적과 중복되므로 0명 리턴
			
			else if (map[nr][nc] == 1) {
				map[nr][nc] = 2;
				killPos.push_back({ nr, nc });
				return 1; //죽일 적이 1명 있으므로 1명 리턴
			}

			else {
				vst[nr][nc] = true;
				q.push({ nr, nc, nv });
			}
		}
	}

	return 0; //궁수가 죽일 수 있는 범위 안에 적이 없으면 0명 리턴
}

void run() {
	for (int r = n - 1; r >= 0; r--) {
		killPos.clear();

		for (int i = 0; i < 3; i++) {
			if (map[r][arr[i]] == 1) { //거리가 1인 적이 있으면 check함수 호출하지 않고 바로 해결
				map[r][arr[i]] = 2;
				killPos.push_back({ r, arr[i] });
				sum++;
				continue;
			}

			sum += check(r, arr[i]); //리턴 된 값을 더해줌
		}

		for (int i = 0; i < killPos.size(); i++)  //2로 바꿔놓은 죽은 적들을 한번에 0으로 처리하기
			map[killPos[i].first][killPos[i].second] = 0;
	}
}

void dfs(int cnt, int k) { //궁수 조합
	if (cnt == 3) {
		int tempMap[N][M] = { 0, }; 
		for (int i = 0; i < n; i++) //배열 백업
			for (int j = 0; j < m; j++) 
				tempMap[i][j] = map[i][j];

		sum = 0;
		run();
		if (MAX < sum) MAX = sum;

		for (int i = 0; i < n; i++) //다시 원래대로
			for (int j = 0; j < m; j++)
				map[i][j] = tempMap[i][j];

		return;
	}

	for (int i = k; i <= m - (K - cnt); i++) {
		arr[cnt] = i;
		dfs(cnt + 1, i + 1);
	}
}

int main() {
	scanf("%d %d %d", &n, &m, &d);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	dfs(0, 0);
	printf("%d\n", MAX);
	
	return 0;
}

ha_ram 5년 전 0

5 5 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1

답 : 3

jjparson님 코드에서 위의 예제를 넣으면 답이 5가 나오네요

jjparson 5년 전 0

ha_ram/ 제 코드에 위의 예제를 넣고 돌려보면 답이 3이라고 나옵니다.. 5라고 나오지 않습니다ㅠㅠ

ha_ram 5년 전 0

jjparson님 코드로 여러가지 반례들 실험해봤는데 틀리는게 없더군요... 그래서 그냥 첨부터 코드 분석해봤습니다.

음.. 결국 문제가 되는 부분을 찾긴찾았는데 왜 이부분이 문제인지는 모르겠네요 ㅠㅠ

그냥 제가 뭔가 위화감 드는 부분을 고치다보니 통과하더라구요

76번째 줄에서 궁수의 위치r을 n-1번째부터 시작하시길래 그 부분을 n번째부터 시작하게 바꾸고 그것에 맞춰서 몇 군데 고쳤더니 통과했습니다.

고친부분을 밑에 코드에 표시해놨으니 한번 봐주세요. 그리고 혹시 왜 n-1부터 시작하면 틀리는지는 저도 알고싶네요..ㅠ

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct Pos {
	int r, c, v;
};

#define pi pair<int, int>
#define N 16
#define M 16
#define K 3

int map[N][M];
int arr[M];
vector<pi> killPos;
int n, m, d, sum, MAX = 0;

int dr[3] = { 0, -1, 0 };
int dc[3] = { -1, 0, 1 };

int check(int r, int c) { // 각각의 궁수가 죽일 적의 위치 찾기
    
    /////////////////////////////////////////////////////r을 n부터 시작했으므로 몇가지 예외처리해줬습니다.
	if(map[r-1][c]==2) return 0;
	if(map[r-1][c]==1){
		killPos.push_back({ r-1,c });
		map[r-1][c] = 2;
		return 1;
	}
    /////////////////////////////////////////////////////
    
	bool vst[N][M] = { false, };
	queue<Pos> q;
    
    ///////////////////////////////////////// r을 r-1로 바꿈
	q.push({ r-1, c, 1 });
	vst[r-1][c] = true;
    ////////////////////////////////////////

	while (!q.empty()) {
		Pos top = q.front();
		q.pop();

		int nv = top.v + 1;
		if (nv > d) continue; //d를 벗어나는 곳은 탐색하지 않음

		for (int i = 0; i < 3; i++) {
			int nr = top.r + dr[i];
			int nc = top.c + dc[i];
			
			if (nr < 0 || nc < 0 || nc >= m) continue;
			if (vst[nr][nc]) continue;

			if (map[nr][nc] == 2) return 0; //앞의 궁수가 이미 죽인 적과 중복되므로 0명 리턴
			
			else if (map[nr][nc] == 1) {
				map[nr][nc] = 2;
				killPos.push_back({ nr, nc });
				return 1; //죽일 적이 1명 있으므로 1명 리턴
			}

			else {
				vst[nr][nc] = true;
				q.push({ nr, nc, nv });
			}
		}
	}

	return 0; //궁수가 죽일 수 있는 범위 안에 적이 없으면 0명 리턴
}

void run() {
    /////////////////////////////////// for문의 r을 n에서부터 시작했습니다.
	for (int r = n; r > 0; r--) {
    ///////////////////////////////////
		killPos.clear();

		for (int i = 0; i < 3; i++) {
            ////////////////////////////////////이부분 주석처리했습니다.
			/*if (map[r][arr[i]] == 1) { //거리가 1인 적이 있으면 check함수 호출하지 않고 바로 해결
				map[r][arr[i]] = 2;
				killPos.push_back({ r, arr[i] });
				sum++;
				continue;
			}*/
            ////////////////////////////////////

			sum += check(r, arr[i]); //리턴 된 값을 더해줌
		}

		for (int i = 0; i < killPos.size(); i++)  //2로 바꿔놓은 죽은 적들을 한번에 0으로 처리하기
			map[killPos[i].first][killPos[i].second] = 0;
	}
}

void dfs(int cnt, int k) { //궁수 조합
	if (cnt == 3) {
		int tempMap[N][M] = { 0, }; 
		for (int i = 0; i < n; i++) //배열 백업
			for (int j = 0; j < m; j++) 
				tempMap[i][j] = map[i][j];

		sum = 0;
		run();
		if (MAX < sum) MAX = sum;

		for (int i = 0; i < n; i++) //다시 원래대로
			for (int j = 0; j < m; j++)
				map[i][j] = tempMap[i][j];

		return;
	}

	for (int i = k; i <= m - (K - cnt); i++) {
		arr[cnt] = i;
		dfs(cnt + 1, i + 1);
	}
}

int main() {
	scanf("%d %d %d", &n, &m, &d);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	dfs(0, 0);
	printf("%d\n", MAX);
	
	return 0;
}

jjparson 5년 전 0

ha_ram/ ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ헉ㅠㅠㅠㅠ

문제되는 부분 찾아주신 것도 너무 감사한데 ㅠㅠㅠㅠㅠ

코드 수정하고 주석까지ㅠㅠㅠㅠㅠㅜㅠㅠㅠㅠㅠㅠㅠ

진짜 너무너무너무너무 감사합니다ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

예제는 다 맞는데 시작하자마자 틀렸습니다 뜹니다ㅜㅜ

jjparson 5년 전 0

ha_ram 5년 전 0

jjparson 5년 전 0

ha_ram 5년 전 0

jjparson 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말