[BaekJoon] 백준 14502번 _ 연구소 for JAVA _ BFS 알고리즘

 

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

14502번: 연구소

 

 

 

 

문제..너무길어

 

 

---

 

BFS 연습하려고 들어갔다.

 

 

정답률이 50프로가 넘길래 만만하게 보고 들어갔는데 1도 모르겠어서~

 

 

다른분꺼 참고함 (https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-14502%EB%B2%88-%EC%97%B0%EA%B5%AC%EC%86%8C-%EC%9E%90%EB%B0%94Java)

 

 

 

 

연구소에 벽을 세울 때 기준이 있을거라고 생각했는데

 

 

모든 경우의 수를 훑는 방식으로 진행되었다.

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


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

public class Baek14502 { // BFS
	public static int N, M, ans = 0;
	public static int[][] map;
	public static int[][] wall_map;
	public static int dx[] = {1, -1, 0, 0};
	public static int dy[] = {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());
		
		map = new int[N][M];
		wall_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());
		}
		
		wall_map = map; // 배열을 이렇게 복사하면 한쪽이 바뀌면 다른 한쪽도 바뀜 (얕은 복사)
		
		make_wall(0);
		
		System.out.println(ans);
				

	}
	
	//벽 세우기 DFS (모든 경우의 수를 훑음)
	public static void make_wall(int index) {
		if(index == 3) { 
			spread_bfs();
			return;
		}
			
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++) 
				if(wall_map[i][j] == 0) {
					wall_map[i][j] = 1;
					make_wall(index + 1);
					wall_map[i][j] = 0; // 다시 원래대로 해놓기
					
				}
	}
	
	//바이러스 퍼트리기 BFS
	public static void spread_bfs() {
		int[][] virus_map = new int[N][M];
		Queue<virus> queue = new LinkedList<>();
		
		// 벽 세운 맵 카피 (깊은 복사)
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++)
				virus_map[i][j] = wall_map[i][j];
		
		
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++)
				if(virus_map[i][j] == 2)
					queue.offer(new virus(i, j)); // 바이러스가 있으면 queue에 넣음
		
		while(!queue.isEmpty()) {
			virus v = queue.poll(); // 꺼내서
			
			for(int i = 0; i < 4; i++) {
				int nx = v.x + dx[i];
				int ny = v.y + dy[i];
				
				if(nx <= -1 || nx >= N || ny <= -1 || ny >= M) continue;
				
				if(virus_map[nx][ny] == 0) {
					virus_map[nx][ny] = 2;
					queue.offer(new virus(nx, ny));
				}
					
			}
		}
		
        
//		for(int i = 0; i < N; i++) {
//			System.out.println();
//			for(int j =0 ; j < M; j++)
//				System.out.print(virus_map[i][j] + " ");
//		}
//		System.out.println();

		
		int count = 0;
		
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++)
				if(virus_map[i][j] == 0)
					count++;
		
		ans = Math.max(count, ans);
		
	}

}

 

 

 

벽을 일일히 세워보는건 DFS를 이용하였다.

 

 

 

 

---

 

남의 코드 살펴보기

 

 

 

코드(https://www.acmicpc.net/source/21403174)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	private static int map[][] = new int[8][8];
	private static int height, width, answer=0;
	private static int[] dx = {-1,0,1,0};
	private static int[] dy = {0,1,0,-1};
	
	
	private static void blockArea() {
		int totalArea = height*width;
		
		for (int first = 0; first < totalArea-2; first++) {
			if (map[first/width][first%width]==0) {
				map[first/width][first%width] = 1;
			}else {	continue;}
			
			for (int second = first+1; second < totalArea-1; second++) {
				if (map[second/width][second%width]==0) {
					map[second/width][second%width] = 1;
				}else {	continue;}
				
				for (int third = second+1; third < totalArea; third++) {
					if (map[third/width][third%width]== 0) {
						map[third/width][third%width] = 1;
					}else {	continue;}
					
					updateAnswer();
					
					map[third/width][third%width] = 0;
				}
				map[second/width][second%width] = 0;
			}
			map[first/width][first%width] = 0;
		}
	}
	
	private static void updateAnswer() {
		int result=0;
		
		for (int x = 0; x < height; x++) {
			for (int y = 0; y < width; y++) {
				if(map[x][y] == 2) {
					DFS(x,y);
				}
			}
		}

		
		for (int x = 0; x < height; x++) {
			for (int y = 0; y < width; y++) {
				if (map[x][y]==0) {
					result++;
				}else if (map[x][y] == 3) {
					map[x][y]=0;
				}
			}
		}

		answer = Math.max(answer, result);
		
		
	}
	
	private static void DFS(int x, int y) {
		int nx,ny;
		for (int i = 0; i < 4; i++) {
			nx = x+dx[i];
			ny = y+dy[i];
			if (isVaildPos(nx, ny) && map[nx][ny]==0) {
				map[nx][ny]=3;
				DFS(nx,ny);
			}
		}
	}
	
	private static boolean isVaildPos(int x, int y) {
		return (x>=0 && x<height && y>=0 && y <width);
	}	
	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		height = Integer.parseInt(st.nextToken());
		width = Integer.parseInt(st.nextToken());
		
		map = new int[height][width];
		
		for (int i = 0; i < height; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < width; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}	

		blockArea();
		
		bw.write(answer+"");
		bw.flush();
		bw.close();
		
	}

}

 

 

 

blockArea() 함수가 벽을 세우는... 함수로 보인다. 나는 DFS로 했는데 저거는.... 저렇게 했구나..

 

 

result의 개수를 구할 때에는 바이러스 때문에 감염된 부분을 3으로 변경했다가 3이면 0으로 바꿔줌으로써

 

 

원래대로 돌려놓았다.

 

 

 

ㅎㅎ어렵군