[연구소문제] DFS 매개변수 질문 !!

[yess98]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n ; 
	static int m ; 
	static BufferedReader br ; 
	static int [][] map; 
	static BufferedWriter bw; 
	static int [] x = {1,-1,0,0};
	static int [] y = {0,0,1,-1};
	static int max = 0 ; 

	public static void main(String [] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in)); 
		bw = new BufferedWriter (new OutputStreamWriter(System.out)); 
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		n = Integer.parseInt(st.nextToken()); 
		m= Integer.parseInt(st.nextToken()); 
		map = new int [n][m];
		for(int i = 0 ; i < n ;  i ++) {
			st = new StringTokenizer(br.readLine()); 
			for(int j = 0 ; j < m ; j ++) {
				map[i][j] = Integer.parseInt(st.nextToken()); 
			}
		}

		dfs(0); 
		bw.write(String.valueOf(max));
		bw.flush();
		bw.close();
		br.close();

	}
	static void find() {
		int [][] copy_map = new int [n][m]; 
		for(int i = 0 ; i < n ; i ++) {
			for(int j = 0 ; j < m ; j ++) {
				copy_map[i][j] = map[i][j]; 
			}
		}
			Queue<int [] > queue = new ArrayDeque<>(); 


		for(int i = 0 ; i < n ; i ++) {
			for(int j = 0 ; j < m ; j ++) {
				if(copy_map[i][j] == 2) {
					int temp [] = {i,j};
					queue.add(temp); 
				}
			}
		}
		while(!queue.isEmpty()) {
			int [] now =queue.poll();
			int tx = now[0]; 
			int ty = now[1]; 
			for(int i = 0 ; i < x.length; i ++) {
				int nx = tx + x[i]; 
				int ny = ty + y[i]; 
				if(nx < 0 || nx >= n || ny < 0 || ny >= m  )continue; 
				if(copy_map[nx][ny] == 0 ) {
					copy_map[nx][ny] = 2; 
					queue.add(new int[] {nx,ny});
				}
			}
		}
		count_virus(copy_map); 

	}
	static void count_virus(int [][] cmap) {
		int cnt = 0 ; 
		for(int i =  0  ; i < n ; i ++)
		{
			for(int j = 0 ; j < m ; j ++) {
				if(cmap[i][j] == 0 ) {
					cnt ++; 
				}
			}
		}
		if(cnt > max) max = cnt; 
	}

	static void dfs(int idx ) {
		if(idx == 3) {
			find(); 
			return ; 
		}
		for(int i= 0 ; i < n ; i ++) {
			for(int j = 0 ; j < m ; j ++) {
				if(map[i][j] == 0 ) {
					map[i][j] = 1; 
					dfs(idx + 1); 
					map[i][j] = 0 ; 
				}
			}
		}
	}
}

위의 코드는 제가 작성한 코드 입니다! DFS에서 @wjdgns7712께서 말씀하신대로 중복이 발생해서 시간이 좀 오래 걸리는 것 같아 중복을 좀 줄이고자 아래와 같이 코드를 바꿔보았는데 이렇게 하면 코드가 제대로 돌아가지 않아요 ㅜ
금일 스터디에서 팀원분들과 함께 고민해보았는데 아직 해결을 못했어요 !! 함께 고민해보면 좋을 것 같아요 ! :)

	static void dfs(int p, int q, int idx ) {
		if(idx == 3) {
			find(); 
			return ; 
		}
		for(int i= 0 ; i < n ; i ++) {
			for(int j = 0 ; j < m ; j ++) {
				if(map[i][j] == 0 ) {
					map[i][j] = 1; 
					dfs(i, j, idx + 1); 
					map[i][j] = 0 ; 
				}
			}
		}
	}

아시는 분들은 코멘트 남겨주시면 감사하겠습니다! 좋은 주말 보내세요 : )

[YeonsangYoon]

매개변수를 전달만 하고 사용을 안하셨네요. 이 문제는 0인 공간을 총 3개를 선택하는 조합 문제이니까
for문 시작 지점을 전달된 매개변수부터 시작해야합니다.

예를 들어 현재 (3, 4) 지점까지 실행된 dfs 호출 스택이면 그 이후로 호출되는 dfs는 (3, 5) ~ (n, m)까지만 선택해야 합니다.

하지만 2차원 배열에서 좌표를 선택하기 위해선 2중 for문을 사용해야 하는데 여기서 문제가 발생해요.
현재 호출 스택이 (3,4)여서 p = 3, q = 4이라고 하고

static void dfs(int p, int q, int idx ) {
	if(idx == 3) {
		find(); 
		return ; 
	}
	for(int i= p ; i < n ; i ++) {
		for(int j = q ; j < m ; j ++) {
			if(map[i][j] == 0 ) {
				map[i][j] = 1; 
				dfs(i, j, idx + 1); 
				map[i][j] = 0 ; 
			}
		}
	}
}

이런 식으로 해버리면 (4, 1)은 좌표들은 (3, 4)보다 뒤에 있어도 선택되지 않아요.

그래서 2중 for문을 1중 for문으로 바꿔서 int 값을 좌표값으로 변환해주면 해결됩니다.

static void dfs(int idx, int start) {
	if(idx == 3) {
		find(); 
		return ; 
	}
	for(int k = start ; k < n*m ; k ++) {
                int i = k / m;
                int j = k % m;
		if(map[i][j] == 0 ) {
			map[i][j] = 1; 
			dfs(idx + 1, k); 
			map[i][j] = 0 ; 
		}
	}
}

이런 식으로 start 매개변수로 현재 위치를 전달받고 k를 start부터 시작한 다음 이를 (i, j)로 변환해주었습니다.

단순한 조합 문제인 nCm을 2차원 배열로 확장한 문제라고 보시면 될 것 같아요.

[wjdgns7712]

와.. 이 방법은 생각못했네요... 멋지십니다!

[yess98]

오 ... 조합을 2차원 배열로 확장한 문제 ... 대박 ...감동이네요 .. ! !!!

[wjdgns7712]

    static void pick(int y, int x, int remain){
        if (remain==0){ // 다 뽑았으면
            spread(); // 바이러스 확산
            return;
        }
        for (int i = y; i < N; i++) { // 이전에 뽑은 위치에서부터 시작
            for (int j = y==i ? x : 0; j < M; j++) {
                if(board[i][j]==0){
                    board[i][j] = 1;
                    pick(i, j, remain-1);
                    board[i][j] = 0;
                }
            }
        }
    }

저는 이렇게 구현했습니다만,

여기서

for (int i = y; i < N; i++) { 
    for (int j = y==i ? x : 0; j < M; j++) {

이렇게 삼항연산으로 조건을 걸어주어 직전위치에서부터 탐색할 수 있게 처리했습니다.

도움이 되실지 모르겠네요!