[백준 알고리즘, 백트레킹, 브루트 포스] 삼성 SW 역량 테스트 문제 :: 14502번 연구소

 

백준 알고리즘

삼성 SW 역량 테스트 문제 모음집이라고

백준 온라인 저지, 백준 알고리즘에 등록되어있는 문제에요

자격증 기출인지 신입 채용을 위한 코딩 테스트 기출인지는 모르겠네요

뭐든간에 이런식으로 나오는거겠죠??

문제를 직접 풀어보니까

빠른 구현능력이 필요할 것 같아요

즉 귀신같이 코딩 잘하는 사람 뽑겠다는... ㅠㅠㅠ

 

1문제만 완벽히 풀어도 면접권이라는 얘기가 있던데

겨우 한 문제 풀어봤네요...

남은 열흘간 화이팅!!!

(그동안 코딩 테스트 공부좀 할걸 ㅠㅠㅠ)

 

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

불러오는 중입니다...

문제를 읽어보면 아 모든 경우를 해봐야겠구나.... 하고 감이 오실거에요!

안오신다면 문제를 좀더 풀어봐야. 크흠..

아무튼 연구소 맵이 있을떄 맵은 빈칸, 벽, 바이러스로 이루어져있어요

빈칸 : 0

벽 : 1

바이러스 : 2

그리고 바이러스(2)는  1로 둘러 쌓여있는 범위 내에서 퍼지게 되어있어요

여기에 벽을 3개 세워서 바이러스가 퍼질 수 없는 영역(안전 영역)을 구해야되요

그러니까 벽 3개 즉 1을 놓을 수 있는곳, 0인 곳에 1을 모두 놓아보는거에요

모든 경우를 다 놓아보고 그래서 안전 영역 크기가 가장 큰 값을 출력하면 끝!!!

 

---

출력

---

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

 

예제 입력

// 디버깅을 위한 간단한 예제
3 4
2 1 0 0
0 0 1 0
1 0 0 0

// 출력
5

 

왜 출력이 5가 될까??

2 1 0 0
0 0 1 0
1 0 0 0

// 다음과 같이 1을 3개 세우면
// 안전 지대는 5칸이 된다(0의 개수)
2 1 0 0
1 1 1 0
1 1 0 0

문제를 이해하면 대충 이런 느낌입니다.

 

저는 브루트 포스와 백트레킹을 이용하여 풀었습니다.

즉 모든 경우의 수를 탐색하여 푸는 방법으로 시도했습니다.

우선 벽을 3개 놓아야해요. 1을 3개 추가해야되죠

그것을 위해 우선 1을 놓을 수 있는 모든 경우의 수를 백트레킹을 이용하여 구하면서 풀었어요

먼저 벽을 놓고 바이러스(2)가 퍼져나갈 곳이 없을때 까지 반복해서 2를 하나씩 채워나갔어요

그렇게 바이러스가 퍼지지 못할 때까지 퍼트린 후 0의 개수 즉, 안전한 곳의 개수를 구해서

그 중에서 가장 큰 값을 Collection을 이용해서 구했어요!!

 

코드는 아래와 같습니다. 주석을 달아 놓았으니 참고하세요!!

전체적인 흐름을 참고하시면 되겠습니다

(참고로 좋은 코드는 아닐 것입니다. 참고만 바랍니다!)

(더 좋고 빠른 방법이 있다면 의견 공유해주시면 감사하겠습니다)

궁금한 부분 있으시면 댓글에 남겨주세요!!

 

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Collections;

class Point {
	int x;
	int y;
	
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

class Main {
	static int[][] lab_map;
	static int[] order_arr;
	static ArrayList<Integer> count_list;
	
	public static void main(String[] args) {
		int i,j;
		Scanner scan = new Scanner(System.in);
		ArrayList<Point> zero_list;
		int[][] new_map;
		boolean[] visited;
		int m, n;
		
		n = scan.nextInt();	// 세로 길이
		m = scan.nextInt();	// 가로 길이
		
		lab_map = new int[n][m];
		visited = new boolean[m*n];
		count_list = new ArrayList<Integer>();

		// Map 입력받기
		for(i=0; i<n; i++) {
			for(j=0; j<m; j++) {
				int temp = scan.nextInt();
				lab_map[i][j] = temp;
			}
		}
		
		zero_list = checkZero(lab_map);	// map에서 값이 0인 좌표 구하기
		int num_zero = zero_list.size();
		
		combination(zero_list, visited, 0, num_zero, 3);	// 모든 경우의 수 검사
		System.out.println(Collections.max(count_list));	// 최댓값 출력
	}
	
	static ArrayList<Point> checkZero(int[][] map) {
		ArrayList<Point> arr_list = new ArrayList<>();
		
		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map[0].length; j++) {
				if(map[i][j] == 0) {
					Point temp_p = new Point(i, j);
					arr_list.add(temp_p);
				}
			}
		}
		return arr_list;
	}
	
    // 2인 값 check
	static ArrayList<Point> checkTwo(int[][] map) {
		ArrayList<Point> arr_list = new ArrayList<>();
		
		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map[0].length; j++) {
				if(map[i][j] == 2) {
					Point temp_p = new Point(i, j);
					arr_list.add(temp_p);
				}
			}
		}
		return arr_list;
	}
	
    // BackTacking을 이용한 모든 조합 검사
    // arr: 조합을 구할 리스트
    // visited: 방문 여부
    // n: 배열 길이
    // r: 구할 조합 개수 ex) arr={1,2,3}, r=2 -> {1,2}, {1,3}, {2,3}
	static void combination(ArrayList<Point> arr, boolean[] visited, int start, int n, int r) {
		if(r==0) {
			count_list.add(insertWall(arr, visited, n));
			
		}
		else {
			for(int i=start; i<n; i++) {
				visited[i] = true;
				combination(arr, visited, i+1, n, r-1);
				visited[i] = false;
			}
		}
	}
	
    // 1(벽) 추가하기
    static int insertWall(ArrayList<Point> arr, boolean[] visited, int n) {
    	int[][] temp_map = deepCopy(lab_map);
    	ArrayList<Point> two_list;
    	
        for(int i=0; i<n; i++) {
            if(visited[i] == true) {
        		Point pnt = arr.get(i);
        		temp_map[pnt.x][pnt.y] = 1;
        		
            }
        }
		
        // 바이러스 퍼트리기
        // 그 다음 둘러 쌓여있지 않은 곳은 2로 바꾸기
        checkVirusSpread(temp_map);
        
        // 0의 개수 세기
        return countZero(temp_map);
    }
    
    static int countZero(int[][] map) {
    	int count =0;
    	for(int i=0; i<map.length; i++) {
    		for(int j=0; j<map[i].length; j++) {
    			if(map[i][j] == 0)
    				count++;
    		}
    	}
    	return count;
    }
    
    // 이차원 배열 deepCopy를 위한 method
    private static int[][] deepCopy(int[][] original2) {
        if(original2 == null) return null;
        int[][] result = new int[original2.length][original2[0].length];
         
        for(int i=0; i<original2.length; i++){
            System.arraycopy(original2[i], 0, result[i], 0, original2[0].length);
        }
         
        return result;
    }
    
    static void checkVirusSpread(int[][] map) {
    	int check = 0;
    	while(true) {
    		ArrayList<Point> list = checkTwo(map);
        	for(int i=0; i<list.size(); i++) {
        		Point pnt = list.get(i);
        		
        		if(pnt.x == 0 && pnt.y == 0) {
        			// 우
            		if(map[pnt.x][pnt.y+1] == 0) {
            			map[pnt.x][pnt.y+1] = 2;
            			check++;
            		}
            		// 하
            		if(map[pnt.x+1][pnt.y] == 0) {
            			map[pnt.x+1][pnt.y] = 2;
            			check++;
            		}
            		continue;
        		}
        		
        		if(pnt.x ==0 && pnt.y == map[0].length) {
        			// 좌
            		if(map[pnt.x][pnt.y-1] == 0) {
            			map[pnt.x][pnt.y-1] = 2;
            			check++;
            		}
            		// 하
            		if(map[pnt.x+1][pnt.y] == 0) {
            			map[pnt.x+1][pnt.y] = 2;
            			check++;
            		}
            		continue;
        		}
        		
        		if(pnt.x == map.length && pnt.y == 0) {
        			// 상
            		if(map[pnt.x-1][pnt.y] == 0) {
            			map[pnt.x-1][pnt.y] = 2;
            			check++;
            		}
        			// 우
            		if(map[pnt.x][pnt.y+1] == 0) {
            			map[pnt.x][pnt.y+1] = 2;
            			check++;
            		}
        			continue;
        		}
        		
        		if(pnt.x == map.length && pnt.y == map[0].length) {
        			// 상
            		if(map[pnt.x-1][pnt.y] == 0) {
            			map[pnt.x-1][pnt.y] = 2;
            			check++;
            		}
            		// 좌
            		if(map[pnt.x][pnt.y-1] == 0) {
            			map[pnt.x][pnt.y-1] = 2;
            			check++;
            		}
        			continue;
        		}
        		
        		if(pnt.x != 0) {
        			// 상
            		if(map[pnt.x-1][pnt.y] == 0) {
            			map[pnt.x-1][pnt.y] = 2;
            			check++;
            		}	
        		}
        		
        		if(pnt.y != 0) {
        			// 좌
            		if(map[pnt.x][pnt.y-1] == 0) {
            			map[pnt.x][pnt.y-1] = 2;
            			check++;
            		}
        		}
        		
        		if(pnt.x != map.length-1) {
            		// 하
            		if(map[pnt.x+1][pnt.y] == 0) {
            			map[pnt.x+1][pnt.y] = 2;
            			check++;
            		}	
        		}
        		
        		if(pnt.y != map[0].length -1) {
        			// 우
            		if(map[pnt.x][pnt.y+1] == 0) {
            			map[pnt.x][pnt.y+1] = 2;
            			check++;
            		}	
        		}
        		
        	}

        	if(check == 0)
        		break;
        	else
        		check=0;
        }	
    }
}

2019/05/11 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 소수] 알고리즘 문제 :: 2581번 소수