글 읽기 - 테스트케이스는 모두 맞는데 어디가 틀린지 모르겠습니다.

andrealgorithm 5년 전 0

아래 소스를 그대로 자바로 옮긴 소스는 맞았는데 C++ 을 왜틀리는지 모르곘네요...
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

int N,L,R,sum,cnt,result;
bool is_end;
int map[21][21]={0};
bool visited[21][21]={0};
int dx[] ={0,0,1,-1};
int dy[] ={1,-1,0,0};

struct Pair{
    int x,y;
};
queue <Pair> q ;
queue <Pair> a;

void init(){
    for(int i =0; i<N; i++){
        for(int j =0; j<N; j++){
            visited[i][j] = false;
        }
    }
}

void bfs(int x, int y){
    int diff =0, each_num =0;
    sum =0; 
    cnt =0;

    sum = map[x][y];
    q.push({x,y});

    while(!q.empty()){
        Pair temp = q.front();
        q.pop();
        visited[temp.x][temp.y] = true;

        for(int i =0; i<4; i++){
            int x1 = temp.x +dx[i];
            int y1 = temp.y +dy[i];

            //맵 범위 필터링
            if(x1<0 || x1>=N || y1<0 || y1>=N)
                continue;
            
            if(visited[x1][y1])
                continue;
            
            diff = abs(map[temp.x][temp.y] - map[x1][y1]);

            //조건 충족시
            if(L <= diff && diff <=R){
                visited[x1][y1] = true;
                sum +=map[x1][y1];
                cnt++;
                a.push({x1,y1}); //그룹핑 된 영역들 좌표 담기 
                q.push({x1,y1}); //다음좌표 이동 
            }
        }
    }
    if(cnt >0){
        is_end = false;
        each_num = sum / (cnt+1);

        while(!a.empty()){
            Pair temp = a.front();
            a.pop();
            map[temp.x][temp.y] = each_num;
        }
    }
    while(!a.empty()){
      a.pop();
    }
}

int main(){
    scanf("%d %d %d",&N,&L,&R);

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

    while(!is_end){
        is_end = true;

        for(int i =0; i<N; i++){
            for(int j =0; j<N; j++){
                if(!visited[i][j]){
                    a.push({i,j});
                    bfs(i,j);
                }
            }
        }
        result++;
        init();
    }
    printf("%d\n",result-1);

    return 0;
}

/*
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
	static int N, L, R,sum,count,result;
	static int map[][];
	static boolean visited[][];
	static boolean is_end;
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,1,-1};
	static Queue<Pair> q = new LinkedList<>();
	static ArrayList<Pair> a = new ArrayList<>();
	
	static class Pair{
		int x; int y;
		Pair(int _x, int _y){
			this.x = _x;
			this.y = _y;
		}
	}
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		visited = new boolean[N][N];

		// 입력 받기
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// 전체 맵 계속 돈다. 전체맵 한번 돌동안 한번도 조건에 성립 안한다 -> while문 나가기,
		// 한번 맵 도는거 끝나야 visited 초기화
		while (!is_end) {
			is_end = true;
//			System.out.printf("=================count = %d===================\n",result);
			
			//맵 전체를 돌동안 한번이라도 조건 충족하면 is_end =false 변경해서 다시 while 문 반복 
			for (int i = 0; i < N; i++) {      
				for (int j = 0; j < N; j++) {
					if (!visited[i][j]) {
						a.add(new Pair(i,j)); //영역 나누는 초기영역 좌표 넣어주기 
						bfs(i, j);          
					}
				}
			}
			result ++;  //인구이동 횟수 
			visited = new boolean[N][N];
		}
		System.out.println(result-1);
	}
	public static void bfs(int x, int y) {
		int diff =0; int each_num =0;
		sum =0; count =0;
		
		sum = map[x][y];      //영역 나누는 초기 좌표의 값 더해주기 
		q.add(new Pair(x,y));
		
		while(!q.isEmpty()) {
			Pair temp = q.poll();
			visited[temp.x][temp.y]= true;
			
			for(int i =0; i<4; i++) {
				int x1 = temp.x +dx[i];
				int y1 = temp.y +dy[i];
				
               //맵 범위 필터링
				if(x1<0 ||x1 >=N || y1<0 || y1>=N)
					continue;
				
               //visit 처리 필터링
				if(visited[x1][y1])
					continue;
				
				diff = Math.abs( map[temp.x][temp.y] - map[x1][y1]);
				
				//조건 충족시 
				if(diff >= L && diff <=R) {
					visited[x1][y1] = true;
					sum += map[x1][y1];
					count++;
					a.add(new Pair(x1,y1));   //구룹핑 된 영역들의 좌표 
					q.add(new Pair(x1,y1));   //다음 좌표 이동 
				}
			}
		}
		if(count >0) {
			is_end = false;
			each_num = sum/ (count+1);
			
			//인구 이동 시작 
			for(Pair temp :a) {
				map[temp.x][temp.y] = each_num;
			}
			//한 영역의 인구이동 끝났으면 그룹핑된 좌표들 clear 
			a.clear();
			
/*			//그리기
			System.out.println("sum= "+sum+", count= "+count+", sum/count= "+each_num);
			for(int i =0; i<N; i++) {
				for(int j =0; j<N; j++) {
					System.out.print(map[i][j] +" ");
				}
				System.out.println();
			}*/
		}
		a.clear();   // ArrayList에 자기 좌표 1나만 들어있을수도 있으므로 
	}
}
*/
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

테스트케이스는 모두 맞는데 어디가 틀린지 모르겠습니다.

andrealgorithm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
