[BaekJoon] 백준 2468번 _ 안전 영역 for JAVA _ DFS 알고리즘

 

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

2468번: 안전 영역

 

 

 

문제

 

 

 

---

 

위 문제도 DFS로 풀어보았다.

 

 

음... 안전 영역을 찾기 위해 0~ 지역의 높이가 가장 높은 곳까지 대입하며 안전 지역이 가장 많은 곳을 찾았다.

 

 

 

 

코드(수정함)

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


public class Baek2468 {
	public static int[][] map;
	public static boolean[][] map_clone; // map에서 안전영역은 1, 아닌곳은 0을 넣은 배열
	public static int N;
	public static int dx[] = {-1, 1, 0, 0};
	public static int dy[] = {0, 0, -1, 1};
    //dx[], dy[]를 전역변수로 선언해서 사용해야 메모리를 많이많이 줄일 수 있다. 중요!
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N]; // map 배열 초기화
		
		
		int max = 0;
		for(int i = 0; i < N; i++) { // 입력된 값 map 배열에 넣고 안전영역 max 높이 찾아놓기
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				max = Math.max(max, map[i][j]);
			}
		}
		
		
		int answer = 0;
		for(int i = 0; i < max + 1; i++) { // 제일 높은곳까지만 넣어서 확인
			int count = 0;
			
			//map_clone 초기화
			map_clone = new boolean[N][N];
			
			//안전 영역 계산값 count[] 배열에 넣기
			for(int j = 0; j < N; j++)
				for(int k = 0; k < N; k++)
					if(!map_clone[j][k] && map[j][k] >= i) {  // 방문x & 높이 이상
						count++;
						safe_dfs(i, j, k);
					}
			
			answer = Math.max(answer, count);
		}
		
		System.out.println(answer);

	}
	
	public static void safe_dfs(int h, int x, int y) {
		
		map_clone[x][y] = true;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx <= -1 || nx >= N || ny <= -1 || ny >= N) continue;
			if(!map_clone[nx][ny] && map[nx][ny] >= h) {
				safe_dfs(h, x + dx[i], y + dy[i]);
				map_clone[x][y] = true;
			}
		}

	}
}

 

 

 

 

지금 (20/01/24 18 : 13) 백준 사이트가 문제가 생겼는지 채점이 안된다.... 403 forbidden 뜨기 때문에

 

 

채점은 못했다. 근데 맞았을 것 같음...

 

 

그래서 성능은.. 나중에 생각나면 올려야겠다~~

 

 

 

그리고 나는 DFS를 풀 때 계속 저 코드를 사용하는데

 

 

 

남의 코드를 살펴보았더니

 

 

 

 

 

이런 느낌으로.. 풀기도 하는 것 같다.

 

 

거의 똑같긴 한데 암튼....~

 

 

 

---

 

 

+ 추가

 

 

 

메모리 초과로 틀려서 코드를 바꿔줬다.

 

 

dx[], dy[]를 safe_dfs() 함수 안에 넣어놨었는데 이렇게 하면 메모리초과가 뜬다^^

 

 

성능

 

 

 

위에가 전역변수로 쓴거고 밑에가 함수 안에 넣어서 사용한거다.

 

 

당연히 재귀를 오지게 해야하니까.. 여러번 선언되면서 메모리 차지가 크겠구나....~

 

 

 

하나 배워간다~