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

제목 어그로에 이끌려서 풀게 된 문제...

전형적인 BFS 문제인데 문제 조건을 잘못 이해해서 좀 헤맸다ㅠ

 

힘이랑 장애물 위치, 높이 정보가 주어지면 힘이 0이 될 때까지 목적지에 도달할 수 있는지 여부를 출력하는 문제이다.

 

한번 이동할 때마다 힘이 1씩 감소하고,

현재 위치보다 이동할 위치의 높이가 높으면 남아있는 힘이 (이동할 위치의 높이 - 현재 위치의 높이)보다 크거나 같아야만 이동할 수 있다. 

난 이 조건을 잘못 이해해서 높이 차만큼 힘도 같이 감소되도록 코드를 작성해서 틀렸다.

해당 조건은 그냥 제약사항일 뿐 힘의 감소에는 영향을 미치지 않는다는 것을 주의하자.

 

아무튼 조건에 맞게 힘을 감소시켜주고 bfs를 돌면서,

목적지에 도착하면 true,

bfs를 끝까지 돌았음에도 목적지에 도달하지 못하면 false를 반환해주면 된다.

 

// 19952_인성문제있어.cpp
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#include <iostream>
#include <cstring>
#include <queue>
#include <utility>
#define MAX 101

int T; // test case
int maze[MAX][MAX];
int visited[MAX][MAX];
int direction[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

bool bfs(int h, int w, int f, int xs, int ys, int xe, int ye) {
	bool result = false;
	queue<pair<int, pair<int, int>>> q;
	q.push(make_pair(f, make_pair(xs, ys)));
	visited[xs][ys] = 1;

	while (!q.empty()) {
		int force = q.front().first;
		int x = q.front().second.first;
		int y = q.front().second.second;
		q.pop();

		if (x == xe && y == ye) { // 도착하면 true
			result = true;
			break;
		}
		if (force == 0) continue;

		for (int i = 0; i < 4; i++) {
			int nx = x + direction[i][0];
			int ny = y + direction[i][1];

			if (nx > h || ny > w || nx < 1 || ny < 1) continue;
			if (visited[nx][ny]) continue;

			if (force >= (maze[nx][ny] - maze[x][y])) {
				visited[nx][ny] = 1;
				q.push(make_pair(force - 1, make_pair(nx, ny)));
			}
		}
	}

	return result;
}

int main()
{
	scanf("%d", &T);
	for (int tc = 0; tc < T; tc++) {
		int h, w, o, f, xs, ys, xe, ye;
		scanf("%d %d %d %d %d %d %d %d",
			&h, &w, &o, &f, &xs, &ys, &xe, &ye);

		memset(visited, 0, sizeof(visited));
		memset(maze, 0, sizeof(maze));
		for (int i = 0; i < o; i++) { // 장애물 정보 입력
			int x, y, l;
			scanf("%d %d %d", &x, &y, &l); // x: 행, y: 열
			maze[x][y] = l;
		}

		if (bfs(h, w, f, xs, ys, xe, ye)) printf("잘했어!!\n");
		else printf("인성 문제있어??\n");
	}

	return 0;
}