백준 14502번 ☆

문제

https://www.acmicpc.net/problem/14502

14502번: 연구소

import java.util.Scanner;

public class Main14502 {

	static int N,M;
	static int[][] labMap;
	static int[][] temp;
	static boolean[][] visited;
	static boolean[][] virus;
	static int[] ax = {1,-1,0,0};
	static int[] ay = {0,0,1,-1};
	static int max;
	
	public static void dfs(int cnt, int x, int y) {
		int sum = 0;
		
		if (cnt == 3) {
			
			for (int i=0; i<N; i++) {
				temp[i] = labMap[i].clone();
				for (int j=0; j<M; j++) {
					virus[i][j] = false;
				}
			}
			
			for (int i=0; i<N; i++) {
				for (int j=0; j<M; j++) {
					if (temp[i][j] == 2 && !virus[i][j]) {
						change(i,j);
					}
				}
			}
			
			for (int i=0; i<N; i++) {
				for (int j=0; j<M; j++) {
					if (temp[i][j] == 0) {
						sum++;
					}
				}
			}
			max = Math.max(max, sum);
			
		} else {
			for (int i=0; i<N; i++) {
				for (int j=0; j<M; j++) {
					if (labMap[i][j]==0 && !visited[i][j]) {
						labMap[i][j] = 1;
						visited[i][j] = true;
						dfs(cnt+1,i,j);
						labMap[i][j] = 0;
						visited[i][j] = false;
					}
				}
			}
		}
	}
	
	public static void change(int x, int y) {
		virus[x][y] = true;
		
		for (int i=0; i<4; i++) {
			int nx = x+ax[i];
			int ny = y+ay[i];
			
			if (nx>=0 && ny>=0 && nx<N && ny<M) {
				if (!virus[nx][ny] && temp[nx][ny] == 0) {
					temp[nx][ny] = 2;
					change(nx, ny);
				}
			}	
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		labMap = new int[N][M];
		temp = new int[N][M];
		visited = new boolean[N][M];
		virus = new boolean[N][M];
		
		for(int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				labMap[i][j] = sc.nextInt();
			}
		}
		
		dfs(0,0,0);
		
		System.out.println(max);
	}
}

1. 일단은 정답. 하지만 좋은 코드인지를 묻는다면 불합

 

2. 정답을 맞추고 코드를 다시 살펴보며 다른 블로그의 글들과 비교를 해보니 불필요한 변수가 너무도 많았다. dfs의 매개변수도 그렇고 virus,visited 사실 이문제에서 굳이 없어도 되는 변수이다. 실제 코테를 보게된다면 이런 요소들이 감점 대상이 될거라고 생각한다. 평소에 문제를 풀며 사용하지 않는 변수는 미리미리 없애서 이런일을 방지하자.

 

3. 문제를 풀다 중간에 알고리즘은 맞는거같은데 왜 자꾸 답이 안나오나 헤맸다. 해답은 change에서 배열을 2로 바꾸고 그 배열로 계속 재귀하니 생기는 문제였다. cnt가 3이 됐을 때 임시배열을 초기화 해줘서 문제를 해결했다. 여기서 중요한것은 얕은 배열복사, 깊은 배열 복사의 차이다. 이전 프로젝트때 개념에 대해 잠시 훑긴했지만 깊게 공부하진 않았다. 이참에 해당 개념에 대해 공부를 해보도록하자.

 

4. 또한 change메소드를 나는 dfs방식으로 풀었는데 다른 블로그의 글들을 보니 bfs로 푸는게 일반적인듯 하다. 해당 방법으로 추가적으로 풀어보자.