[BOJ/JAVA] 백준 14502번 : 연구소 (공부 더 해보기)

14502번: 연구소

---

 

• 코드

정답 코드 : 벽을 dfs 알고리즘 방식으로 세우면서 3개를 세울 때 dfs로 안전하지 않은 곳에 바이러스를 퍼뜨린 다음에 안전한 지역의 수를 return 받는다. 받은 return 값의 최대 값을 출력.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {	
	static int[][] array;
	static int N, M, max = 0;
    static int[] x = {-1, 1, 0, 0};
    static int[] y = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		array = new int[N][M];

		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) 
				array[i][j] = Integer.parseInt(st.nextToken());			
		}
		
		dfs(0);
		System.out.println(max);

	}
	
    // 벽 기둥 3개를 세우기 위한 함수
	// DFS 재귀 형식
    private static void dfs(int count) {
    	// base case
        if(count == 3) {
            max = Math.max(max, bfs());
            return;
        }
        
        for(int i = 0; i < N; i++) {
            for(int j = 0 ; j < M; j++) {
                if(array[i][j] == 0) {
                    array[i][j] = 1;
					dfs(count+1);
                    array[i][j] = 0;
                }
            }
        }
    }
	
	private static int bfs() {		
		// 임시 배열 (기존 배열을 유지하기 위함)
        int[][] spreadVirusArray = new int[N][M];
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
            	spreadVirusArray[i][j] = array[i][j];
        
        Queue<int[]> queue = new LinkedList<>();
        
        // 바이러스 인 곳을 queue에 위치를 추가해줌.
        for(int i = 0; i < N; i++)
        	for(int j = 0; j < M; j++)
        		if(spreadVirusArray[i][j] == 2) queue.add(new int[] {i,j});
        
        // 벽으로 보호되지 않은 곳은 virus를 퍼뜨림
        // BFS
        while(!queue.isEmpty()){
            int location[] = queue.poll();

            for(int direction = 0; direction < 4; direction++){
                int r = location[0] + x[direction];
                int c = location[1] + y[direction];

                if(r >= 0 && c >= 0 && r < N && c < M) {
                    if(spreadVirusArray[r][c] == 0) {
                    	spreadVirusArray[r][c] = 2;
                        queue.add(new int[] {r,c});
                    }
                }
            }
        }                
        
        // 바이러스가 퍼지지 않은 지역 수
		int count = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++)
				if(spreadVirusArray[i][j] == 0) count++;
		}
		
        return count;
    }
}

 

 

현재 까지 메모리, 속도 개선해보려고 노력하고 있는 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {	
	static int[][] array, spreadVirusArray;
	static int N, M, max = 0;
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		array = new int[N][M];
		spreadVirusArray = new int[N][M];

		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) 
				array[i][j] = Integer.parseInt(st.nextToken());			
		}
		
		dfs(0);
		System.out.println(max);

	}
    
    private static int[][] xy = {
            {1, 0}, {0, 1},
            {-1, 0}, {0, -1}
    };
    
    // 벽 기둥 3개를 세우기 위한 함수
	// DFS 재귀 형식
    private static void dfs(int count) {
    	// base case
        if(count == 3) {
            max = Math.max(max, bfs());
            return;
        }
        
        for(int i = 0; i < N; i++) {
            for(int j = 0 ; j < M; j++) {
                if(array[i][j] == 0) {
                    array[i][j] = 1;
					dfs(count+1);
                    array[i][j] = 0;
                }
            }
        }
    }
	
	private static int bfs() {		
		// 임시 배열 (기존 배열을 유지하기 위함)
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
            	spreadVirusArray[i][j] = array[i][j];
        
        Queue<int[]> queue = new LinkedList<>();
        
        // 바이러스 인 곳을 queue에 위치를 추가해줌.
        for(int i = 0; i < N; i++)
        	for(int j = 0; j < M; j++)
        		if(spreadVirusArray[i][j] == 2) queue.add(new int[] {i,j});
        
        // 벽으로 보호되지 않은 곳은 virus를 퍼뜨림
        // BFS
        while(!queue.isEmpty()){
            int location[] = queue.poll();

            for (int[] direction : xy) {
                int r = location[0] + direction[0];
                int c = location[1] + direction[1];

                if(r >= 0 && c >= 0 && r < N && c < M) {
                    if(spreadVirusArray[r][c] == 0) {
                    	spreadVirusArray[r][c] = 2;
                        queue.add(new int[] {r,c});
                    }
                }
            }
        }                
        
        // 바이러스가 퍼지지 않은 지역 수
		int count = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++)
				if(spreadVirusArray[i][j] == 0) count++;
		}
		
        return count;
    }
}

 

 

메모리 적게 쓰는 방법

 

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int[][] array;
	static int N, M, answer;
    static int[] x = {-1, 1, 0, 0};
    static int[] y = {0, 0, -1, 1};

	public static void main(String[] args) throws Exception {
		SetData();	
		blockArea();
		System.out.println(answer);
	}

	// 데이터
	private static void SetData() throws Exception  {
		InputReader in = new InputReader(System.in);
		
		N = in.readInt();
		M = in.readInt();		
		array = new int[N][M];
		answer = 0;

		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) 
				array[i][j] = in.readInt();			
		}
	}
	
	private static void blockArea() {
		int totalArea = N*M;
		
		for (int first = 0; first < totalArea-2; first++) {
			if (array[first/M][first%M]==0) {
				array[first/M][first%M] = 1;
			}else {	continue;}
			
			for (int second = first+1; second < totalArea-1; second++) {
				if (array[second/M][second%M]==0) {
					array[second/M][second%M] = 1;
				}else {	continue;}
				
				for (int third = second+1; third < totalArea; third++) {
					if (array[third/M][third%M]== 0) {
						array[third/M][third%M] = 1;
					}else {	continue;}
					
					updateAnswer();
					
					array[third/M][third%M] = 0;
				}
				array[second/M][second%M] = 0;
			}
			array[first/M][first%M] = 0;
		}
	}
	
	private static void updateAnswer() {
		int result=0;
		
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < M; y++) {
				if(array[x][y] == 2) {
					DFS(x,y);
				}
			}
		}

		
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < M; y++) {
				if (array[x][y]==0) {
					result++;
				}else if (array[x][y] == 3) {
					array[x][y]=0;
				}
			}
		}

		answer = Math.max(answer, result);		
	}
	
	private static void DFS(int a, int b) {
		int r,c;
		for (int i = 0; i < 4; i++) {
			r = a+x[i];
			c = b+y[i];
			
			if(r < 0 || c < 0 || r >= N || c >= M || array[r][c] != 0) continue;

			array[r][c]=3;
			DFS(r,c);
			
		}
	}
    
	private static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public int readInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			if (filter != null) {
				return filter.isSpaceChar(c);
			}
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}