글 읽기 - 미세먼지 확산 부분 관련 질문

rladufbf 4년 전 0

3차원 배열을 이용하여 문제를 해결해야 된다고 생각했습니다.

5보다 큰경우 큐에 집어넣었고 큐가 빌때까지 확산을 시행하여 다음과 같이 문제를 해결하고자 했는데

확산에서 자꾸 맞지 않는 값이 나오네요.

이렇게 풀면 안되나요??
풀어도 된다면 어느 부분이 틀린걸까요??

import java.util.*;


public class BOJ_17144_SW_EXEXAM {

	static int R,C,T;
	static int arr [][][];
	static Queue<Node> q ;
	static int xx [] = {-1,0,0,1};
	static int yy [] = {0,1,-1,0};
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		
		R = sc.nextInt();
		C = sc.nextInt();
		T = sc.nextInt();
		int time = 0;
		
		arr = new int [R+1][C+1][1001];
		
		q = new LinkedList<Node>();
		
		for(int i =0;i<R;i++) {
			for(int j =0;j<C;j++) {
				arr[i][j][0] = sc.nextInt();		
			
			}
		}
		
		while(time!=T) {
			time=time+1;
			
			for(int i =0;i<R;i++) {
				for(int j =0;j<C;j++) {
					if(arr[i][j][time-1]>4) {
						q.add(new Node(i,j));
					}
					if(arr[i][j][time-1]<=4) {
						arr[i][j][time]=arr[i][j][time-1];
					}
				}
			}
			
			
		
		while(!q.isEmpty()) {
			Node now = q.remove();
			int nowx = now.x;
			int nowy = now.y;
			
			int splitvalue = arr[nowx][nowy][time-1]/5;
			
			int splitway = 4;
			
			for(int i =0;i<4;i++) {
				int nextx = nowx+xx[i];
				int nexty = nowy+yy[i];
			
				if(nextx<0||nextx>=C||nexty<0||nexty>=R) {
					splitway--;
					continue;
				}
				
				if(arr[nextx][nexty][time-1]==-1) {
					splitway--;
					continue;
				}
				
				arr[nextx][nexty][time] +=splitvalue;
				
			}
			
			arr[nowx][nowy][time]+=arr[nowx][nowy][time-1]-splitvalue*splitway;
		}
		
		/*
		//확산 완료
		for(int i =0;i<R;i++) {
			for(int j =0;j<C;j++) {
				System.out.print(arr[i][j][time]+" ");
			}
			System.out.println();
		}
	    */
		
		
		}
		
	
	}
	
	
	static class Node{
		int x;
		int y;
		Node(int x, int y){
			this.x=x;
			this.y=y;
		
		}
	}

}

exponential_e 4년 전 1

코드 전체를 올려주신게 맞나요?

확산하고 나서 공기 청정기에 의해 위쪽과 아래쪽이 순환이 되어야하는데 이에 해당하는 코드가... 없는거 같은데요..?

아닌가요?

exponential_e 4년 전 0

그리고 가장 자리 부분의 먼지 데이터가 문제가 있어서 확인해 본 결과

63번째 줄에 if(nextx<0||nextx>=C||nexty<0||nexty>=R) R, C가 바꼈습니다.

rladufbf 4년 전 1

먼저 공기확산 작업 이후에 공기청정기 이동 작업을 수행해야된다고 생각햇습니다.

현장에서 시험을 본 취준생인데 어직 실력이 부족하다보니 저부분에서 막혀서 이렇게 푸는게 맞는가 싶어서 질문올렸습니다...

exponential_e 4년 전 1

저의 경우엔 임시 배열을 2차원으로 하나더 짜서 덮어 씌우는 방식으로했는데요.

작성자님 코드는 메모리 제한만 안걸린다면... 괜찮을 것 같습니다.

올려주신 코드를 자세히 봤는데, 작동방식도 사실 배열만 다르게 짰지 제 코드와 거의 동일하게 도는 것으로 보였습니다.

실제로 제가 말씀드린 줄만 수정해서 돌려봤는데, 제 코드랑 예제 1의 먼지 확산은 동일하게 수행되었구요..

저도 뭐 실력이 엄청 좋은 편도 아니고 취준생인지라....ㅎㅎ 처음에 코드 봤을때 뭔가 빠져있는 것 같아서 여쭤본거였습니다.

취준 화이팅하세요!

exponential_e 4년 전 1

다른 실력 좋은 분들께서 첨언을 해주시면 좋겠는데.. 제 답변을 참고하셔서 일단은 끝까지 문제 풀어보시면 좋을 것 같아요~

rladufbf 4년 전 1

저 방식대로 문제를 풀어보니 1번째 먼지 확산, 공기청정기 순환은 제대로 작성했는데 2번째 먼지 확산이 되는 부분에서 오류가 발생하네요.

실례가 안된다면 코드 부탁드려도 될까요....ㅠ_ㅠ

rladufbf@naver.com

으로 보내주시면 감사하겠습니다...ㅠㅠ;;;;

exponential_e 4년 전 1

보내드리는건 어려운일이 아닌데.. 그게 도움이 될만한 일인지는 모르겠어요.ㅠ

일단 현재까지 진행하신 코드라도 댓글로 올려 주실 수 있나요??

rladufbf 4년 전 0

이렇게 작성했습니다.

1번째 확산과 공기청정기 이동은 제대로 되는데

2번째로 넘어갈 경우 result를 받아와야 되는데 어떻게 구현해야될지 감이 안오네요...

3차원 정렬로 구현한게 틀린방법인가 싶기도하고.

import java.util.*;


public class BOJ_17144_SW_EXEXAM {

	static int R,C,T;
	static int arr [][][];
	static Queue<Node> q ;
	static ArrayList<Integer> airx;
	static int xx [] = {-1,0,0,1};
	static int yy [] = {0,1,-1,0};
	static int result [][];
	static int sum = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		
		R = sc.nextInt();
		C = sc.nextInt();
		T = sc.nextInt();
		int time = 0;
		
		arr = new int [R+1][C+1][1001];
		airx = new ArrayList<>();
		q = new LinkedList<Node>();
		
		
		for(int i =0;i<R;i++) {
			for(int j =0;j<C;j++) {
				arr[i][j][0] = sc.nextInt();
				
			}
		}
		
	
		result = new int[R+1][C+1];
		
		while(time!=T) {
			time=time+1;
			
			if(time==1) {
			for(int i =0;i<R;i++) {
				for(int j =0;j<C;j++) {
					if(arr[i][j][time-1]>4) {
						q.add(new Node(i,j));
					}
					if(arr[i][j][time-1]<=4) {
						arr[i][j][time]=arr[i][j][time-1];
					}
			
				}
			}
			}else {
				for(int i =0;i<R;i++) {
					for(int j =0;j<C;j++) {
						arr[i][j][time] = result[i][j];
						if(result[i][j]>4) {q.add(new Node(i,j));}
						if(result[i][j]<=4) {arr[i][j][time]=result[i][j];}
					}
					
				}
			}
			
		
		while(!q.isEmpty()) {
			Node now = q.remove();
			int nowx = now.x;
			int nowy = now.y;
			
			int splitvalue = arr[nowx][nowy][time-1]/5;
			
			int splitway = 4;
			
			for(int i =0;i<4;i++) {
				int nextx = nowx+xx[i];
				int nexty = nowy+yy[i];
			
				if(nextx<0||nextx>=R||nexty<0||nexty>=C) {
					splitway--;
					continue;
				}
				
				if(arr[nextx][nexty][time-1]==-1) {
					splitway--;
					continue;
				}
				
				arr[nextx][nexty][time] +=splitvalue;
				
			}
			
			arr[nowx][nowy][time]+=arr[nowx][nowy][time-1]-splitvalue*splitway;
		}
		
		
		System.out.println(time+"번째 미세먼지 확산");
		//확산 완료
		for(int i =0;i<R;i++) {
			for(int j =0;j<C;j++) {
				System.out.print(arr[i][j][time]+" ");
			}
			System.out.println();
		}
		System.out.println();
		
		for(int i =0;i<R;i++) {
			for(int j =0;j<C;j++) {
				result[i][j]=arr[i][j][time];
			}
		}
	
		
		//확산 성공. -> 이제 공기청정기를 이용하여 순환을 해야됨.
		for(int i =0;i<R;i++) {
			if(result[i][0]==-1) {
				airx.add(i);
			}
		}
		
		int x1 = airx.get(0);
		int x2 = airx.get(1);
		
		result[x1][1]=0;
		result[x2][1]=0;
		
		for(int i=x1;i<=x2;i++) {
			for(int j =2;j<C;j++) {
				result[i][j]= arr[i][j-1][time];
			}
		}
		
		for(int i=0;i<R;i++) {
			if(i==x1||i==x2) {
				continue;
			}
			if(i<x1) {
				result[i][C-1] = arr[i+1][C-1][time];
			}
			if(i>x2) {
				result[i][C-1] = arr[i-1][C-1][time];
			}
		}
		
		for(int j = C-2;j>=0;j--) {
			result[0][j]=arr[0][j+1][time];
			result[R-1][j] = arr[R-1][j+1][time];
		}
		
		for(int i = 0;i<R-1;i++) {
			if(i==x1||i==x2||i==0||i==R-1) {continue;}
			
			if(i<x1) {
				result[i][0] = arr[i-1][0][time];
			}
			if(i>x2) {
				result[i][0] = arr[i+1][0][time];
			}
			
		}
		
		System.out.println(time+"번째 공기청정기 후 ");
		// 미세먼지 총합 결과 도출
		for(int i =0;i<R;i++) {
			for(int j =0;j<C;j++) {
				System.out.print(result[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
		
		}
		
		
		
		for(int i =0;i<R;i++) {
			for(int j =0;j<C;j++) {
				if(result[i][j]>0) {
				sum+=result[i][j];
				}
			}
		}
		
		System.out.println("정답은 : "+sum);
		
	}
	
	
	static class Node{
		int x;
		int y;
		Node(int x, int y){
			this.x=x;
			this.y=y;
		
		}
	}

}

rladufbf 4년 전 1

문제 해결했습니다.

3차원 배열로 처음에 확산상황을 정했으면 공기청정기 이후에도 3차원배열로 생각해야 되는데 2차원 배열로 생각해서 문제를 해결하려다 보니

대응이 되지 않아서 문제 해결에 어려움을 겪었었네요.

감사합니다. exponential_e 님 덕분에 잘 배웠습니다!!!

exponential_e 4년 전 0

도움이 된게 있었나 싶네요..ㅎㅎ

글을 이제봐서 ㅠㅠ 죄송합니다.

아무튼 생각하셨던 방법으로 혼자 해결하셨다니 다행입니다!

roigh12 4년 전 0

작성자님 혹시 acm-icpc 같이 나가실 의향 있으시면 연락주세요. 010-5039-4015 동국대 4학년입니다.

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

문제

문제

출처

ICPC

미세먼지 확산 부분 관련 질문

rladufbf 4년 전 0

exponential_e 4년 전 1

exponential_e 4년 전 0

rladufbf 4년 전 1

exponential_e 4년 전 1

exponential_e 4년 전 1

rladufbf 4년 전 1

exponential_e 4년 전 1

rladufbf 4년 전 0

rladufbf 4년 전 1

exponential_e 4년 전 0

roigh12 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말