[백준] 19952 인성문제있어??

1. 문제

www.acmicpc.net/problem/19952

19952번: 인성 문제 있어??

2. 접근방법

평범한 bfs 완탐 문제

입력 받을게 엄청 많은데

그냥 맵형태로 입력주진 ..

 

어쨋든

맵을 만들고 장애물 위치에 장애물의 높이를 넣어주고

현재 위치부터 bfs로 돌아가며 자신의 체력보다 높은 장애물 위치는 못가는 것만 생각해주며 목적지에 도착하는지만 보면 된다.

 

체력에 따라 다르게 처리해줄 부분이 있나? 생각해볼수도 있지만 사실 한칸 이동하면 체력이 1씩 무조건 깍이므로

bfs로 이동하면 어느 한 점을 갈때 남아있는 현재 체력이 어떤 상황보다 가장 높은것이 보증이 되므로 신경쓸 필요가 없다.

 

자신의 남은 체력보다 높은 장애물인가? 만 처리해주면 되는 bfs문제이다.

 

3. 자바 코드

package Gold;

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

public class P19952인성문제있어 {
	static class node{
		int row;
		int col;
		int power;
		public node(int row, int col, int power) {
			super();
			this.row = row;
			this.col = col;
			this.power = power;
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int testcase = Integer.parseInt(br.readLine());
		
		for(int tc  = 1 ; tc <= testcase ; tc++) {
			st = new StringTokenizer(br.readLine());
			
			int H = Integer.parseInt(st.nextToken());
			int W = Integer.parseInt(st.nextToken());
			int O = Integer.parseInt(st.nextToken());
			int F = Integer.parseInt(st.nextToken());
			int SX = Integer.parseInt(st.nextToken())-1;
			int SY = Integer.parseInt(st.nextToken())-1;
			int GX = Integer.parseInt(st.nextToken())-1;
			int GY = Integer.parseInt(st.nextToken())-1;
			int [][] map = new int[H][W];
			boolean [][] visited = new boolean[H][W];
			map[GX][GY] = -1;
			for(int i = 0 ; i < O ; i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken())-1;
				int y = Integer.parseInt(st.nextToken())-1;
				int L = Integer.parseInt(st.nextToken());
				map[x][y] = L;
			}
			Queue<node> que = new LinkedList<node>();
			que.offer(new node(SX, SY, F));
			visited[SX][SY] = true;
			int dr[] = {1,-1,0,0};
			int dc[] = {0,0,1,-1};
			boolean flag = false;
			gg:while(!que.isEmpty()){
				node now = que.poll();
				for(int i = 0 ; i < 4 ; i++) {
					int row = now.row + dr[i];
					int col = now.col + dc[i];
					
					int power = now.power;
					if(row<0 || col < 0 || row>= H || col>= W)
						continue;
					if(map[row][col] - map[now.row][now.col] >= power )
						continue;
					if(visited[row][col])
						continue;
					if(map[row][col] == -1) {
						flag = true;
						break gg;
					}
					visited[row][col] = true;
					que.offer(new node(row, col, power-1));
				}
			}
			System.out.println(flag? "잘했어!!":"인성 문제있어??");
		}
	}
}

4. 마치며

다른 조건은 필요없는 단순한 bfs문제라 어렵지 않았다.