백준 - 죽음의 비

문제 설명

격자가 주어지고 출발지에서 도착지 까지는 체력이 소모된다.

출발지에서 도착지 까지 체력이 0이 되지 않으면서 가장 빠르게 이동하는 횟수를 구하는 문제이다.

출발지에서 도착지까지 해당 격자 공간안에 우산이 주어지면 우산의 내구성을 얻어 체력이 1씩 감소되는 경우를 우산으로 대체할 수 있다.

주의사항

• 일반 방문 T/F처리로는 목적지까지 온전히 갈수없다.
  • 왜냐하면 빠르게 가는 것보다 체력이 도착지까지 0이 안되는 경우가 더 우선순위이기 때문이다.

TRY

• DFS, 맨헤튼 거리를 통한 BFS 탐색 [FAIL]
• 방문 배열을 int로 선언한 현재 체력+우산의 내구도에 대한 흔적을 남기고 진행하기
  • 이렇게 되면 가장 먼저 빠르게 목적지 인근에서 체력이0이 된 경우에도 뒤에 있는 노드들은 계속 진행할 수 있다.

풀이

static int n, UMBRELLA, answer = Integer.MAX_VALUE;
	static char map[][];
	static int v[][];
	static int dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1};

	static class Node {
		int y, x, health, umbrella, cnt;

		public Node(int y, int x) {
			this.y = y;
			this.x = x;
		}

		public Node(int y, int x, int health, int umbrella, int cnt) {
			this.y = y;
			this.x = x;
			this.health = health;
			this.umbrella = umbrella;
			this.cnt = cnt;
		}

		public boolean hasUmbrella() {
			return this.umbrella > 0;
		}

		public boolean hasHealth() {
			return this.health > 0;
		}

		public void decreaseUmbrella() {
			this.umbrella -= 1;
		}

		public void decreaseHealth() {
			this.health -= 1;
		}

		public void replaceUmbrella() {
			this.umbrella = UMBRELLA;
		}

	}

	/**
	 * 멚헤튼 거리로 판명한다면 거리가 가까운 순으로 갈텐데 그때 더 멀어질 수 도 있어 도착못할 수도 있다.
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(reader.readLine());

		n = Integer.parseInt(st.nextToken());
		int health = Integer.parseInt(st.nextToken());
		UMBRELLA = Integer.parseInt(st.nextToken());

		Node start = null;
		map = new char[n][n];
		v = new int[n][n];

		for (int i = 0; i < n; i++) {
			map[i] = reader.readLine().toCharArray();

			for (int j = 0; j < n; j++) {
				if (map[i][j] == 'S') {
					start = new Node(i, j, health, 0, 0);
				}
			}
		}

		LinkedList<Node> q = new LinkedList();
		q.offer(start);
		while (!q.isEmpty()) {
			Node cur = q.poll();

			if (map[cur.y][cur.x] == 'E') {
				answer = cur.cnt;
				break;
			}

			for (int i = 0; i < 4; i++) {
				int ny = dy[i] + cur.y;
				int nx = dx[i] + cur.x;

				if (isOutOfRange(ny, nx))
					continue;
				if (cur.umbrella <= 0 && cur.health <= 0)
					continue;
				if (v[ny][nx] >= cur.health + cur.umbrella)
					continue;

				Node next = new Node(ny, nx, cur.health, cur.umbrella, cur.cnt + 1);

				if (map[ny][nx] == 'U') {
					next.replaceUmbrella();
				}

				if (next.hasUmbrella()) {
					next.decreaseUmbrella();
				} else if (next.hasHealth()) {
					next.decreaseHealth();
				}

				v[ny][nx] = cur.health + cur.umbrella;
				q.offer(next);
			}
		}

		System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
	}

	static boolean isOutOfRange(int ny, int nx) {
		return ny < 0 || nx < 0 || ny >= n || nx >= n;
	}