[백준] 2842 집배원 한상덕 - JAVA

2842번: 집배원 한상덕 (acmicpc.net)

2842번: 집배원 한상덕

 

 

풀이

알고리즘 파악

DFS + 투 포인터

 

피로도를 구하는 방식은 최고 높이 - 최저 높이 이다.

즉, P를 포함한 모든 K를 방문하는 경우의 수 중, 최고 높이와 최저 높이의 차가 가장 작은 경우를 구하는것 이다.

 

투포인터로 최저 높이와 최고 높이를 구한뒤, 해당 최저 높이와 최고 높이로 모든 K와 P를 방문할수 있는지를 DFS를 통해 확인한다. 

 

구현

1. 마을의 모든 고도를 TreeSet에 저장 한다(자동 오름차순 정렬+중복값 제거) 이후 배열에 다시 저장한다.

 

2. 투포인터를 이용해 해당 배열에서 최저높이와 최고높이를 설정한다. (left와 right)

 

3. 해당 최저 높이와 최고 높이로 모든 K와 P를 방문할수 있는지를 알아 봐야 한다. 이를 DFS로 구현한다.

 

4. 만약 DFS를 통해 방문이 가능하면 최저높이를 올린다. 이는 최저 높이<= 최고높이 까지 실행한다. 방문이 불가능하면 최고 높이를 올린다.   

 

import java.io.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
	static int n,maxK,K;
	static char[][] map; //위치 배열
	static int[][] alt; //고도 배열
	static int[] alt_arr; //오름차순 고도 정렬
	static int[] dx = {-1,1,0,0,-1,-1,1,1};
	static int[] dy = {0,0,-1,1,-1,1,-1,1};
	static boolean p_check; //P 체크

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw  =new BufferedWriter(new OutputStreamWriter(System.out));
	    n = Integer.parseInt(br.readLine());
	    map = new char[n][n];
	    alt = new int[n][n];
	    TreeSet<Integer> set = new TreeSet<>(); //정렬을 위한 TreeSet
	    int[] begin = new int[2];
        
	    for(int i=0; i<n; i++)
	    {
	    	String str = br.readLine();
	    	for(int j=0; j<n; j++) 
	    	{
	    	map[i][j] = str.charAt(j);	
	    	if(map[i][j] == 'P')
	    	{
	    		begin[0] = i; begin[1]=j;
	    	}
	    	else if(map[i][j] == 'K') maxK++;
	    	}
	    }
	    for(int i=0; i<n; i++)
	    {
	    	StringTokenizer st =new StringTokenizer(br.readLine()," ");
	    	for(int j=0; j<n; j++) {alt[i][j] = Integer.parseInt(st.nextToken()); set.add(alt[i][j]); }
	    }
	    alt_arr = new int[set.size()];
	    int idx=0;
	    for(int num:set) alt_arr[idx++] = num;
	    
	    int left=0, right =0; 
	    int min= Integer.MAX_VALUE;
	    boolean end =false;
	    for(int i=0; i<alt_arr.length; i++) ////투 포인터
	    {
	    	right = i;
	        while(left<=right) 
	        {
	        	K = maxK;
	        	p_check = false;
	        	dfs(begin[0],begin[1],alt_arr[right],alt_arr[left],new boolean[n][n]); //탐색
	        	if(K==0 && p_check) //성공
	        	{
	        		min = Math.min(min,alt_arr[right]-alt_arr[left]);
	        		if(left==right) end = true; //종료(피로도 0)
	        		left++;
	        	}
	        	else break; //실패 - 최고 높이 증가
	        }
	        if(end) break;
	    }
	   
	    bw.write(Integer.toString(min));
        bw.flush();
        bw.close();
        br.close();
	}
	//탐색 시작
	static void dfs(int x, int y,int max,int min,boolean[][] visit)
	{
		for(int i=0; i<8; i++)
		{
		  int nx = x+dx[i], ny =y+dy[i];
		  
		  if(check_move(nx,ny,max,min,visit))
		  {  
			if(map[nx][ny]=='P') p_check = true;  
			if(map[nx][ny]=='K') K--; 
			dfs(nx,ny,max,min,visit);
		  }
		}
	}
	
    // 해당위치의 고도가 MAX 보다 작거나 같고 MIN 보다 크거나 같아야 한다.
	static boolean check_move(int x, int y,int max,int min,boolean[][] visit)
	{
		if(x<0 || x==n|| y<0 || y==n || visit[x][y] || alt[x][y] >max || alt[x][y] <min ) return false;
		visit[x][y] = true;
		return true;
	}
}