글 읽기 - 뭐가 문제 일까요 ㅜㅜㅜㅜㅜㅜㅜㅜㅜ

sohyeon24 6년 전 0

dfs, bfs 썼는데 안돌아가요 ㅜㅜ

뭐가 문제 인지 모르겠습니다 ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ

import java.util.*;
import java.awt.Point;;

public class Main {
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static int n;
	static int m;
	static int[][] board;
	static Queue<Point> virus = new LinkedList<Point>();
	static int result = 0;
	static int temp;
	static int[][] check;
	static int standard = 0;
	
	static int bfs(){
		Queue<Point> q = new LinkedList<Point>();
		for(Point p : virus){
			q.add(p);
		}
		
		while(!q.isEmpty()){
			Point now = q.poll();
			for(int k=0; k<4; k++){
				int nx = now.x + dx[k];
				int ny = now.y + dy[k];
				
				if(nx>=0 && nx <n && ny>=0 && ny <m && check[nx][ny]==0 && board[nx][ny]==0){
					check[nx][ny] = 2;
					temp++;
					q.add(new Point(nx,ny));
				}
			}
		}
		
		return standard - temp;
	}
	
	
	static void dfs(int cnt, int idx){
		if(cnt == 3){
			temp = bfs();
			result = result > temp ? result : temp;
			temp = 0;
			return;
		}
		int x = idx/m;
		int y = idx%m;
		check[x][y] = 1;
		for(int i=idx+1; i<n*m; i++){
			int nx = i/m;
			int ny = i%m;
			if(check[nx][ny] == 0 && board[x][y] == 0)
				dfs(cnt+1, i);
		}
		check[x][y] = 0;
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		board = new int[n][m];
		
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				board[i][j] = sc.nextInt();
				if(board[i][j] == 0) standard++; 
				else if(board[i][j] == 2) virus.add(new Point(i,j));
			}
		}
		
		for(int i=0; i<n*m; i++){
			int x = i/m;
			int y = i%m;
			if(board[x][y] == 0){
				check = new int[n][m];
				dfs(0,i);
			}
		}
		
		System.out.println(result);

	}
}

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

문제

문제

출처

ICPC

뭐가 문제 일까요 ㅜㅜㅜㅜㅜㅜㅜㅜㅜ

sohyeon24 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말