글 읽기 - 9525-Attacking Rooks 런타임 오류//코드가 길어요

annemeier 9년 전 0

런타임 에러가 나서 어디가 오류인지 확인이 안되요

도와주세요ㅠㅠ

코드가 길어서 죄송합니다.. 어떻게 풀었는지 요약해볼게요

1. 세로선과 가로선을 구분해 두개의 보드에 저장한다.

2. 교차하는 지점에 룩을 놓는다고 하면

하나의 점에 룩을 놓으면 그 점을 지나는 가로선, 세로선에는 다른 룩을 놓을 수 없다.

그러므로 최대한 많은 세로선과 가로선이 쌍을 짓게 만든다.

3. 오직 하나의 선과 연결할 수 있는 가로선 또는 세로선은 다른 선과 연결한다.

연결되는 지점에 룩을 놓는다.

더 이상, 하나의 선만 연결되는 가로선 또는 세로선이 없으면

남은 선이 적은쪽은 모두 연결되므로 이 수만큼 룩을 놓을 수 있다.

#include<stdio.h>
#include<stdlib.h>
int main(){
	int n, i, j, k, x, y, ch, ans = 0, xtem=0, ytem=0, ch1, ch2;
	int row, col;
	char **board1;
	char **board2;
	int **matrix;
	scanf("%d", &n);
	row = 0; col = 0;
	board1 = (char**)malloc(sizeof(char*)*n);// 보드1을 동적할당
	for (i = 0; i < n; i++)
		board1[i] = (char*)malloc(sizeof(char)*n);
	for (i = 0; i < n; i++)//                   보드1을 입력받음
		for (j = 0; j < n; j++)
			scanf(" %c",&board1[i][j]);
	board2 = (char**)malloc(sizeof(char*)*n);// 같은 크기의 보드2를 만듬
	for (i = 0; i < n; i++)
		board2[i] = (char*)malloc(sizeof(char)*n);
	for (i = 0; i < n; i++)//                   보드1을 보드2에 복사
		for (j = 0; j < n; j++)
			board2[i][j] = board1[i][j];
	for (i = 0; i < n; i++){//                  보드1을 세로로 구분함
		if (board1[i][0] == '.'){//             그 줄에서 첫번째 칸이 빈칸이면 세로줄수(row)에 1을 더함
			row++; board1[i][0] = '0' + row;//  그 칸에 몇번째 세로줄인지 표시
		}
		for (j = 0; j < n - 1; j++){
			if (board1[i][j] == 'X'&&board1[i][j + 1] == '.'){//전칸에 X가 있고 다음칸이 빈칸이면 1 더함
				row++; board1[i][j + 1] = '0' + row;//          몇번째 세로줄인지 표시
			}
			else if (board1[i][j] != 'X')board1[i][j] = '0' + row;//위 경우가 아니면 몇번째인지 표시
		}
		if (board1[i][j] == '.')
			board1[i][j] = '0' + row;
	}
	for (i = 0; i < n; i++){//                   보드2를 가로로 구분함
		if (board2[0][i] == '.'){
			col++; board2[0][i] = '0' + col;
		}
		for (j = 0; j < n - 1; j++){
			if (board2[j][i] == 'X'&&board2[j + 1][i] == '.'){
				col++; board2[j + 1][i] = '0' + col;
			}
			else if (board2[j][i] != 'X') board2[j][i] = '0' + col;
		}
		if (board2[j][i] == '.')
			board2[j][i] = '0' + col;
	}
	matrix = (int**)malloc(sizeof(int*)*row);//  세로선의 수와 가로선의 수를 곱한만큼의 행렬만듬
	for (i = 0; i < row; i++)
		matrix[i] = (int*)malloc(sizeof(int)*col);

	for (i = 0; i < row; i++)//              행렬을 초기화하고
		for (j = 0; j < col; j++)
			matrix[i][j] = 0;
	for (i = 0; i < n; i++)//                가로선과 세로선이 교차하는 부분에 1을 대입
		for (j = 0; j < n; j++)
			if (board1[i][j] != 'X'){
				x = board1[i][j] - '0';
				y = board2[i][j] - '0';
				matrix[x - 1][y - 1] = 1;
			}
	for (k = 0; k < row + col; k++){//       가로선 또는 세로선이 충분히 없어질 수 있을만큼
		for (i = 0; i < row; i++){//         하나의 가로선과 교차하는 세로선을 그 가로선과 연결
			ch = 0;
			for (j = 0; j < col; j++)//      연결될 수 있는 가로선의 수(ch)를 셈
				if (matrix[i][j] == 1){
				ch++; xtem = i; ytem = j;
				}
			if (ch == 1){//                  그 수(ch)가 1이면 그점에 룩을 놓고
				for (j = 0; j < col; j++)//  그 점을 지나는 선이 다른 선과 만날 수 없도록 0대입
					matrix[xtem][j] = 0;
				for (j = 0; j < row; j++)
					matrix[j][ytem] = 0;
				ans++;//                     답(ans)에 1을 더함
				break;
			}
		}
		for (i = 0; i < row; i++){//         하나의 세로선과 교차하는 가로선을 그 세로선과 연결
			ch = 0;
			for (j = 0; j < col; j++)//      연결될 수 있는 세로선의 수(ch)를 셈
				if (matrix[j][i] == 1){
				ch++; xtem = j; ytem = i;
				}
			if (ch == 1){//                  
				for (j = 0; j < col; j++)
					matrix[xtem][j] = 0;
				for (j = 0; j < row; j++)
					matrix[j][ytem] = 0;
				ans++;
				break;
			}
		}
	}
	ch2 = 0; ch1=0;
	for (i = 0; i < row; i++){//              하나 이상의 선과 연결되는(ch!=0) 세로선의 갯수(ch1)를 셈
		ch = 0;
		for (j = 0; j < col; j++)
			if (matrix[i][j] == 1)
				ch++;
		if (ch != 0)
			ch1++;
	}
	for (i = 0; i < col; i++){//              하나 이상의 선과 연결되는(ch!=0) 가로선의 갯수(ch2)를 셈
		ch = 0;
		for (j = 0; j < row; j++)
			if (matrix[j][i] == 1)
				ch++;
		if (ch != 0)
			ch2++;
	}
	if (ch1 < ch2)ch = ch1;//                  둘중 작은 수를 답(ans)에 더함
	else ch = ch2;
	ans += ch;
	printf("%d",ans);
}

sujin 9년 전 4

n의 크기가 100이므로 가로선의 갯수는 최대 5000개 정도까지 가능할 것입니다.

그러면 board1[i][j+1] = '0' + row; 에서 board1은 char 형 배열이므로 오버플로우가 발생하고

x = board1[i][j] - '0'; 에서 x가 음수값을 가지게될 수 있으며,

matrix[x - 1][y - 1] = 1; 재앙이 일어납니다

annemeier 9년 전 1

감사합니다! 깨달음을 얻었습니다

방금 수정해서 제출했더니 시간초과가 뜨네요 :)

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

문제

문제

출처

ICPC

9525-Attacking Rooks 런타임 오류//코드가 길어요

annemeier 9년 전 0

sujin 9년 전 4

annemeier 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말