JUNGOL/Intermediate_Coder/그래프탐색-BFS/1082 : 화염에서탈출(SLIKAR)

Intermediate_Coder/그래프탐색-BFS/화염에서탈출(SLIKAR)

---

문제                                            

재우는 중간계(middle-earth)에서 유명한 용사이다.

 

어느날 사람들에게 부탁 받은 마물 퇴치를 신속히 해결하고 집으로 돌아가려고 하는데, 

마법의 숲에서 재우를 추적하고 있던 불의 마법사 무길이와 마주치게 되었다. 

무길이는 재우를 잡기 위해서 화염 마법을 시전하였고 어느덧 숲은 화염으로 가득차고 있었다. 

재우는 무길이가 화염을 풀어 놓은 숲에서 신속히 요새로 귀환하고자 한다!

 

숲의 지도는 R행과 C열로 이루어져있다. 

비어있는 칸은 '.'로 표시되고, 불은 '*'로, 바위는 'X'로 표시되어있다. 

용사의 집은 'D'로 표현되고, 재우가 처음에 서있는 위치는 'S'로 표시된다.

 

매 분마다 재우는 인접한 4개의 칸(상, 하, 좌, 우)으로 이동할 수 있다. 

불은 매 분마다 인접한 4개의 칸에 불을 옮긴다.

재우는 불과 바위를 지나지 못한다. 

불은 바위와 요새에 옮겨지지 않는다.

 

재우가 탈출을 할 수 있을 때 몇 분 만에 탈출 할 수 있는지 알아보는 프로그램을 작성하라.

 

입력 형식                                     

입력의 첫번째 줄에는 50이하의 정수인 R과 C가 입력된다.

다음 줄부터 지도가 입력되며, 이는 R개의 줄로 이루어져있다. 

각 R개의 줄에는 C개의 문자가 입력된다. 

지도에는 정확히 하나의 용사의 집과 하나의 시작 위치가 입력된다.

 

출력 형식                                     

재우가 숲에서 용사의 집으로 돌아올 수 있을 때 최단 시간(분)을 출력하고,

만약 탈출이 불가능할 경우 "impossible"을 출력한다.

 

입력 예                                        

3 3       | 3 3               | 3 6          | 8 6
D.*       | D.*               | D...*.       | D...*.
...         | ...                 | .X.X..      | .XXX..
.S.        | ..S               | ....S.        | .X*...

                                                   | .XS...

                                                   | .XXX..

                                                   | ......

                                                   | XXXXX.

                                                   | *.....

 

출력 예                                        

3          | impossible   | 6             | 13

---

EscapeFromFire.h

#pragma once
#include <iostream>
#include <queue>
#include <vector>

#include "../../Base.h"

using std::queue;
using std::vector;

class EscapeFromFire : public Base
{
private:
	struct Point
	{
		int x, y;
		int turn;

		Point() : x(0), y(0), turn(0) {}
		Point(int x, int y, int turn = 0) : x(x), y(y), turn(turn) {}
	};

	void SimulateFire();
	int CalculateEscapeTime();

	bool PossibleToGo(int x, int y, int turn);

	bool IsInMap(int x, int y);
	bool IsArrive(int x, int y);

protected:
	void Code() override;

private:
	const int xDir[4]{ 0, 0, -1, 1 };
	const int yDir[4]{ -1, 1, 0, 0 };

	const int EMPTY{ 999'999'999 };
	const int BLOCK{ 0 };

	int r{}, c{};
	int map[50][50]{};

	queue<Point> q;
	Point startPos;
	Point endPos;
};

 

EscapeFromFire.cpp

void EscapeFromFire::Code()
{
	std::cin >> r >> c;

	char ch;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			std::cin >> ch;
			map[i][j] = EMPTY;

			if (ch == 'S')
			{
				startPos = { j, i };
				map[i][j] = BLOCK;
			}
			else if (ch == 'D')
			{
				endPos = { j, i };
				map[i][j] = BLOCK;
			}
			else if (ch == 'X')
			{
				map[i][j] = BLOCK;
			}
			else if (ch == '*')
			{
				map[i][j] = BLOCK;
				q.push({ j, i });
			}
		}
	}

	SimulateFire();

	int escapeTime{ CalculateEscapeTime() };
	if (escapeTime == BLOCK)
		std::cout << "impossible";
	else
		std::cout << escapeTime;
}

/// <summary>
/// 불이 번지는 과정을 저장한다.
/// </summary>
void EscapeFromFire::SimulateFire()
{
	while (!q.empty())
	{
		Point p{ q.front() };
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextX{ p.x + xDir[i] }, nextY{ p.y + yDir[i] };
			int nextTurn{ p.turn + 1 };
			if (IsInMap(nextX, nextY) && map[nextY][nextX] == EMPTY)
			{
				map[nextY][nextX] = nextTurn;

				q.push({ nextX, nextY, nextTurn });
			}
		}
	}

	// 사람은 집에 들어갈 수 있도록 수정
	map[endPos.y][endPos.x] = EMPTY;
}

/// <summary>
/// 탈출하는 데 걸리는 시간을 반환한다.
/// </summary>
/// <returns>탈출한 시간(불가능한 경우 -1)</returns>
int EscapeFromFire::CalculateEscapeTime()
{
	q.push(startPos);
	while (!q.empty())
	{
		Point p{ q.front() };
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextX{ p.x + xDir[i] }, nextY{ p.y + yDir[i] };
			int nextTurn{ p.turn + 1 };
			if (IsInMap(nextX, nextY) && PossibleToGo(nextX, nextY, nextTurn))
			{
				if (IsArrive(nextX, nextY))
				{
					return nextTurn;
				}

				q.push({ nextX, nextY, nextTurn });

				map[nextY][nextX] = BLOCK;
			}
		}
	}

	return BLOCK;
}

/// <summary>
/// 이동 가능한지 여부를 반환한다.
/// </summary>
/// <param name="x">x 좌표</param>
/// <param name="y">y 좌표</param>
/// <param name="turn">진행 턴</param>
/// <returns>이동 가능 여부</returns>
bool EscapeFromFire::PossibleToGo(int x, int y, int turn)
{
	return turn < map[y][x];
}

/// <summary>
/// 맵 범위에 벗어나는지 여부를 반환한다.
/// </summary>
/// <param name="x">x 좌표</param>
/// <param name="y">y 좌표</param>
/// <returns>맵을 벗어나는지 여부</returns>
bool EscapeFromFire::IsInMap(int x, int y)
{
	bool xInMap{ 0 <= x && x < c };
	bool yInMap{ 0 <= y && y < r };
	return xInMap && yInMap;
}

/// <summary>
/// 도착했는지 여부를 반환한다.
/// </summary>
/// <param name="x">x 좌표</param>
/// <param name="y">y 좌표</param>
/// <returns>도착 여부</returns>
bool EscapeFromFire::IsArrive(int x, int y)
{
	return x == endPos.x && y == endPos.y;
}

 

---

실행 결과 Success(100)

 

※ 같은 동작을 한다면 코드를 최대한 단순한 버전으로 만드는 게 좋다.

---

 

코드 해설

기본적인 아이디어는 BFS를 분리하는 것이다. 불이 이동하는 것과 사람이 이동하는 것을 동시에 계산하는 건 너무 복잡하니 둘 중 하나를 먼저 계산해두고 시간에 따른 결과로 저장해 두고 이후 나머지를 계산할 때 사용하면 되는 것이다.

 

이 문제에서는 불이 먼저 계산되어야 하니 불을 먼저 시뮬레이션하고 이후 용사가 이동하는 것을 BFS로 체크하면 된다.

이를 위해서 태울 수 없는 부분과 시작 위치, 끝 위치, 처음 불이 있는 위치를 저장해둔다.

			if (ch == 'S')
			{
				startPos = { j, i };
				map[i][j] = BLOCK;
			}
			else if (ch == 'D')
			{
				endPos = { j, i };
				map[i][j] = BLOCK;
			}
			else if (ch == 'X')
			{
				map[i][j] = BLOCK;
			}
			else if (ch == '*')
			{
				map[i][j] = BLOCK;
				q.push({ j, i });
			}

 

이후 불에 대해 BFS를 진행하며 시간 경과에 따른 값을 저장해 둔다. 0은 처음 불이 있거나 바위가 있어 이동이 불가능한 값이고 1 이상의 값은 해당 숫자에 해당하는 턴이 지났을 때 불이 붙는 것을 뜻한다.

void EscapeFromFire::SimulateFire()
{
	while (!q.empty())
	{
		Point p{ q.front() };
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextX{ p.x + xDir[i] }, nextY{ p.y + yDir[i] };
			int nextTick{ p.tick + 1 };
			if (IsInMap(nextX, nextY) && map[nextY][nextX] == EMPTY)
			{
				map[nextY][nextX] = nextTick;

				q.push({ nextX, nextY, nextTick });
			}
		}
	}

 

그런데 용사의 집은 용사가 이동이 가능해야 하므로 불을 시뮬레이션 한 뒤에는 이동 가능한 값으로 수정해줘야 한다.

	// 사람은 집에 들어갈 수 있도록 수정
	map[endPos.y][endPos.x] = EMPTY;

 

이렇게 되면 모든 준비는 끝났고 이제 준비된 맵을 바탕으로 BFS를 돌리면 된다.

이때, 위에서 설명한 대로 맵의 값보다 현재 턴이 더 큰 경우 이동이 불가능할 것이라는 것만 주의하면 된다.

bool EscapeFromFire::PossibleToGo(int x, int y, int turn)
{
	return turn < map[y][x];
}

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제 출처

COCI 2006/2007 Contest1 Task4- 화염에서탈출(SLIKAR) > 문제은행 | JUNGOL : 정보올림피아드&알고리즘

JUNGOL