글 읽기 - 연구소 문제 질문드립니다...

dlarudtn8 4년 전 0

재귀함수로 벽3개 세운 다음 BFS이용하여 바이러스 찾고 0개수가 가장 큰 값을 출력하려고 하는데

답이 안나와서 배열을 출력해봤는데 BFS부분에서 오류가 있는지 2가 있는데도 옆에있는 0이 2로 안바뀌는 경우가 많네요..

몇시간째 찾아보는데 도저히 뭐가 잘못된건지 모르겠습니다 ㅠㅠ

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	static int lab[][];
	static int temp[][];
	static int move[] = {-1,1};
	
	static int result = 0;
	static int width;
	static int height;
	
	static Queue que_x = new LinkedList();
	static Queue que_y = new LinkedList();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		width = sc.nextInt();
		height = sc.nextInt();
		
		lab = new int[width][height];
		temp = new int[width][height];
		
		
		for(int i=0;i<width;i++) {
			for(int j=0;j<height;j++) {
				lab[i][j] = sc.nextInt();    
			}
		}
		
		
		for(int i=0;i<width;i++) {
			for(int j=0;j<height;j++) {
				if(lab[i][j]==0) {
						for(int m=0;m<width;m++) {
							for(int n=0;n<height;n++) {
								temp[m][n] = lab[m][n];     ///////임시 배열에 원본을 복사한다
							}
						}
						
					temp[i][j] = 1;
					add_wall(1);
					temp[i][j]=0;
				}
			}
		}
		
		
		System.out.println(result);
		
	}
		
	
	
	static void add_wall(int cnt) {
		if(cnt==3) {
			scan_virus();  ////추가된 벽의 개수가 3개가 되면 바이러스 검색한다
			return;
		}
		else {
			for(int i=0;i<width;i++) {
				for(int j=0;j<height;j++) {
					if(temp[i][j]==0) {
						temp[i][j] = 1;
						add_wall(cnt+1);
						temp[i][j] = 0;
					}
				}
			}
		}
	}
	
	static void scan_virus() {
		boolean visited[][] = new boolean[width][height];
		for(int i=0;i<width;i++) 
			for(int j=0;j<height;j++) 
				visited[i][j] = false;
		
		int empty = 0;
		que_x.clear();
		que_y.clear();
		
		for(int m=0;m<width;m++){
			for(int n=0;n<width;n++){		
				if(temp[m][n]==2){				
					que_x.add(m);
					que_y.add(n);
					}
			}
		}
					while(que_x.isEmpty()==false && que_y.isEmpty()==false) {
						int X = (int)que_x.poll();
						int Y = (int)que_y.poll();
						
						////////////////X+1, X-1 가 0 인지 검사하고 0이면 큐에 추가한다/////////////
						for(int i=0;i<2;i++) {
							if(X+move[i]>=0 && X+move[i]<width) {
								if(temp[X+move[i]][Y]==0 && visited[X+move[i]][Y]==false) {
									visited[X+move[i]][Y] = true;
									temp[X+move[i]][Y] = 2;
									que_x.add(X+move[i]);
									que_y.add(Y);
									
								}
							}
						}////////////////X+1, X-1 가 0 인지 검사하고 0이면 큐에 추가한다/////////////
						
						
						
						////////////////Y+1, Y-1 가 0 인지 검사하고 0이면 큐에 추가한다///////////
						for(int i=0;i<2;i++) {
							if(Y+move[i]>=0 && Y+move[i]<height) {
								if(temp[X][Y+move[i]]==0 && visited[X][Y+move[i]]==false) {
									visited[X][Y+move[i]] = true;
									temp[X][Y+move[i]] = 2;
									que_x.add(X);
									que_x.add(Y+move[i]);
								}
							}
						}////////////////Y+1, Y-1 가 0 인지 검사하고 0이면 큐에 추가한다///////////
						
						
						
					}//while문 끝
					
					for(int i=0;i<width;i++) {
						for(int j=0;j<height;j++) {
							if(temp[i][j]==0)
								empty++;
						}
					}//////////////0의 개수에 따라서 empty값 증가시킨다
					
					
					result = Math.max(empty, result);
	}
}

shg9411 4년 전 1

잠깐 봤는데 119번 라인 이상해보이네요.

dlarudtn8 4년 전 0

앗 막 수정하다가 이상하게 올렸네요 119번 라인 que_y.add 입니다 죄송합니다ㅜㅜ

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

문제

문제

출처

ICPC

연구소 문제 질문드립니다...

dlarudtn8 4년 전 0

shg9411 4년 전 1

dlarudtn8 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말