글 읽기 - 어떤 부분이 틀렸는지 잡아주시면 감사하겠습니다.

le_effort 4년 전 0

백트래킹이 조금 미숙해서 이부분에서 잘못 된 것 같은데 어떤 건지 찾지를 못하겠네요...

다른 부분이 잘못 된 것 일수도 있지만

의심 되는 부분은

30-36라인

41-61라인인데

무엇이 잘못됐고 왜 잘못된건지 설명해주시면 정말 감사하겠습니다

글봐주셔서 감사합니다.

import java.io.*;
import java.util.*;
public class Main {
	static int n,m;
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	static int arr[][];
	static boolean visited[][];
	static int ans=0;
	static boolean dfs_visited[][];
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        
        arr = new int[n][m];
      
        dfs_visited = new boolean[n][m];
        
        for(int i=0; i<n; i++) {
        	String[] tt = br.readLine().split(" ");
        	for(int j=0; j<m; j++) {
        		arr[i][j]=Integer.parseInt(tt[j]);
        	}
        }
        // 0 - 빈칸  ,  1 - 벽 ,  2- 바이러스
        
        for(int i=0; i<n; i++) {
        	for(int j=0; j<m; j++) {
        		if(!dfs_visited[i][j] && arr[i][j]==0) {
        			dfs(i,j,0);
        		}
        	}
        }
        
        System.out.println(ans);
        
	}
	public static void dfs(int r, int c, int level) {
		if(level==3) {
			int x = bfs(r,c);
			//System.out.println("x= " + x);
			ans = Math.max(ans,x);
			return ;
		}
		dfs_visited[r][c]= true;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(!dfs_visited[i][j] && arr[i][j]==0) {
					dfs_visited[i][j]=true;
					arr[i][j]=1;
					dfs(i,j,level+1);

				}
			}
		}
		dfs_visited[r][c]=false;
		arr[r][c]=0;
	}
	public static int bfs(int r ,int c) {
		 visited = new boolean[n][m];
		int copy[][] = new int[n][m];
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				copy[i][j]=arr[i][j];
			}
		}
		int cnt=0;
		
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(r,c));
		visited[r][c] =true;
		
		while(!q.isEmpty()) {
			Node a = q.poll();
			for(int i=0; i<4; i++) {
				int x_1 = a.x+dx[i];
				int y_1 = a.y+dy[i];
				if(x_1>=0 && y_1>=0 && x_1<n && y_1<m) {
					if(!visited[x_1][y_1] && copy[x_1][y_1]!=1) {
						q.add(new Node(x_1,y_1));
						visited[x_1][y_1]=true;
						copy[x_1][y_1]=2;
					}
				}
			}
		}
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(copy[i][j]==0) {
					cnt++;
				}
			}
		}
		/*for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				System.out.print(copy[i][j]);
			}
			System.out.println();
		}*/
		return cnt;
	}
}
class Node{
	int x;
	int y;
	Node(int x , int y){
		this.x=x;
		this.y =y;
	}
}

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

문제

문제

출처

ICPC

어떤 부분이 틀렸는지 잡아주시면 감사하겠습니다.

le_effort 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말