백준 19952 <인성 문제있어??>

잘 읽어보면 간단한 DFS 또는 BFS문제이다.

 

처음에 우선순위 큐로 풀어야 되나 라는 고민을 잠시 했지만 높이의 차만큼 에너지가 감소되는 것이 아니기 때문에 그냥 Queue로도 풀이가 가능하다.

 

전체 코드

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

public class Main{

	public static class car{
		int x;
		int y;
		int energe;
		public car(int x, int y, int energe) {
			super();
			this.x = x;
			this.y = y;
			this.energe = energe;
		}
		
	}
	static int result,map[][],t,h,w,o,f,xs,ys,xf,yf,dir[][]= {{-1,0},{0,1},{1,0},{0,-1}};
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));
		t=Integer.parseInt(kb.readLine());
		for(int tc=1;tc<=t;tc++) {
			result=0;
			StringTokenizer st=new StringTokenizer(kb.readLine());
			h=Integer.parseInt(st.nextToken());
			w=Integer.parseInt(st.nextToken());
			o=Integer.parseInt(st.nextToken());
			f=Integer.parseInt(st.nextToken());
			xs=Integer.parseInt(st.nextToken());
			ys=Integer.parseInt(st.nextToken());
			xf=Integer.parseInt(st.nextToken());
			yf=Integer.parseInt(st.nextToken());
			map=new int[h+1][w+1];
			for(int i=0;i<o;i++) {
				st=new StringTokenizer(kb.readLine());
				map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]=Integer.parseInt(st.nextToken());
			}
			bfs();
			if(result==0)
				System.out.println("인성 문제있어??");
			else
				System.out.println("잘했어!!");
		}
		
	}
	private static void bfs() {
		// TODO Auto-generated method stub
		boolean visit[][]=new boolean[h+1][w+1];
		Queue<car> q=new LinkedList<car>();
		visit[xs][ys]=true;
		q.add(new car(xs,ys,f));
		while(!q.isEmpty()) {
			car next=q.remove();
			if(next.x==xf&&next.y==yf) {
				result=1;
				return;
			}
			for(int i=0;i<4;i++){
				int x1=next.x+dir[i][0];
				int y1=next.y+dir[i][1];
				if(x1<=0||x1>h||y1<=0||y1>w||visit[x1][y1]||map[x1][y1]-map[next.x][next.y]>next.energe||next.energe==0) {
					continue;
				}

				visit[x1][y1]=true;
				q.add(new car(x1,y1,next.energe-1));
			}
		}
	}
	

}