글 읽기 - 9337번 문제 예외처리 할 것이 있나요?

hist0613 10년 전 0

문제에서 얘기한대로 "가장 많이 바뀔 수 있는 색깔로 greedy 하게 진행하면 된다" 해서 그렇게 진행했는데

틀렸습니다 가 나오네요

예제도 잘 나오는데;; 따른 예외가 있기도 힘들 것 같은데 무슨 문제일까요...

코드는 메인 부분과 count_next_color 부분만 올렸습니다

while(testcase--){
		int N;
		int board[22][22] = {0};
		int check[22][22] = {0};
		int num_color_selected[7] = {0};
		int move_cnt = 0;

		// 입력 파트
		cin>>N;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				char temp_in;
				cin>>temp_in;
				board[i][j] = temp_in - '0';
			}
		}

		check[1][1] = 1;
		move_next_color(board, N, board[1][1], check);

		//같은 색으로 채워질 때까지 무한 루프
		int last_color = board[1][1];
		while(true){
			if(all_color_is_same(board, N) == true) break;	// 모든 색깔이 [1][1] 과 같은지 확인

			int max_color = 0, max_count = 0;
			for(int color = 1; color <= 6; color ++){		
				if(color == last_color) continue;			// 이전에 바꾼 색깔과 달라야함
				int count_next = count_next_color(board, N, color, check);	// 현재 보드 상황에서 color로 얼마나 바뀔 수 있는지 확인
				if(count_next > max_count){					// max 보다 더 크다면 변경
					max_color = color;
					max_count = count_next;
				}
			}

			move_next_color(board, N, max_color, check);	// board 와 check 배열을 실제로 바꿔줌 (count_next_color 함수는 두 배열이 const 로 되어있음)
			last_color = max_color;
			num_color_selected[max_color] ++;
			move_cnt++;
		}

		cout<<move_cnt<<endl;
		for(int color = 1; color <= 6; color++) cout<<num_color_selected[color]<<' ';
		cout<<endl;
	}

///////////////////////////////////////////////////////////////////////////////


int count_next_color(const int board[22][22], int N, int color, const int _check[22][22]){
	int count = 0;
	queue<Position> q;

	int check[22][22] = {0};
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			check[i][j] = _check[i][j];
		}
	}

	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			if(board[i][j] == color && (check[i-1][j] || check[i+1][j] || check[i][j-1] || check[i][j+1])){
				Position p;
				p.x = i, p.y = j;
				q.push(p);
			}
		}
	}
	while(!q.empty()){
		++count ;
		Position curr = q.front();
		q.pop();
		int x = curr.x, y = curr.y;
		if(check[x][y] == 1) continue;
		check[x][y] = 1;
		if(x < N && !check[x + 1][y] && board[x + 1][y] == color){
			Position p;
			p.x = x + 1, p.y = y;
			q.push(p);
		}
		if(x > 1 && !check[x - 1][y] && board[x - 1][y] == color){
			Position p;
			p.x = x - 1, p.y = y;
			q.push(p);
		}
		if(y < N && !check[x][y + 1] && board[x][y + 1] == color){
			Position p;
			p.x = x, p.y = y + 1;
			q.push(p);
		}
		if(y > 1 && !check[x][y - 1] && board[x][y - 1] == color){
			Position p;
			p.x = x, p.y = y - 1;
			q.push(p);
		}
	}
	return count;
}

Nada 10년 전 0

bfs를 수행할 때 check[x][y] == 1 일 때 continue 하셨는데

그전에 ++count를 하셨네요

전체 소스가 아니여서 대충 눈에 집히는 부분만 설명해 드릴 수밖에 없네요

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

문제

문제

출처

ICPC

9337번 문제 예외처리 할 것이 있나요?

hist0613 10년 전 0

Nada 10년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말