5427 불
문제 링크
- 내 풀이
bfs를 통해 먼저 불들을 번지게 하고, 사람을 이동시켰다. 시간을 측정하기 위해 각 사람 요소마다 시간을 저장하여 이동을 막았는데 다른 사람은 더 효율적으로 풀었다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
struct ele
{
int r, c, t;
};
constexpr int dr[4] = { -1, 1, 0, 0 };
constexpr int dc[4] = { 0, 0, -1, 1 };
int T, w, h;
char m[1000][1000];
int chk[1000][1000];
pair<int, int> S;
vector<ele> F;
int isGoal(ele e) {
if (e.r == 0 || e.r == h - 1 || e.c == 0 || e.c == w - 1)
return 1;
return 0;
}
int solve()
{
queue<ele> fq, sq;
for (ele f : F)
fq.push(f);
sq.push({ S.first, S.second, 1 });
chk[S.first][S.second] = 1;
m[S.first][S.second] = '.';
int t = 1;
while (!sq.empty())
{
// fire move
while (!fq.empty())
{
if (fq.front().t != t)
break;
for (int d = 0; d < 4; d++)
{
ele nEle = fq.front();
nEle.r += dr[d];
nEle.c += dc[d];
nEle.t += 1;
if (nEle.c < 0 || nEle.c >= w || nEle.r < 0 || nEle.r >= h || m[nEle.r][nEle.c] != '.')
continue;
m[nEle.r][nEle.c] = '*';
fq.push(nEle);
}
fq.pop();
}
// Sanggeun move
while (!sq.empty())
{
if (isGoal(sq.front()))
return sq.front().t;
if (sq.front().t != t)
break;
for (int d = 0; d < 4; d++)
{
ele nEle = sq.front();
nEle.r += dr[d];
nEle.c += dc[d];
nEle.t += 1;
if (m[nEle.r][nEle.c] == '.' && !chk[nEle.r][nEle.c])
{
sq.push(nEle);
chk[nEle.r][nEle.c] = 1;
}
}
sq.pop();
}
t += 1;
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int result;
string in;
cin >> T;
// . # @ *
while (T--)
{
memset(chk, 0, sizeof(chk));
F.clear();
cin >> w >> h;
for (int r = 0; r < h; r++)
{
cin >> in;
for (int c = 0; c < w; c++)
{
m[r][c] = in[c];
if (in[c] == '@')
S = { r, c };
else if (in[c] == '*')
F.push_back({ r, c, 1 });
}
}
result = solve();
if (result == -1)
cout << "IMPOSSIBLE\n";
else
cout << result << "\n";
}
}
- 다른 사람 풀이 (1등은 아니지만 이해가 잘되는 코드, 내 코드보다는 빨랐음)
눈여겨 볼 점
- person.size()를 size에 while문 조건문에서 할당하는 모습(쓰지는 않았지만..)
- char배열에 문장을 직접 입력을 받을 수 있다.(\0를 위해 1개 더 많은 배열크기?)
- 큐의 팝 횟수를 얼마나 해야하는지 생각해본 풀이!!! 나같이 무식하게 시간을 같이 저장하지 않았다.
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int tc, w, h;
char building[1001][1001];
bool visited[1001][1001];
int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};
int bfs() {
queue<pair<int, int>> person;
queue<pair<int, int>> fire;
// 사람, 불 찾고
for (int r = 0; r < h; r++) {
for (int c = 0; c < w; c++) {
if (building[r][c] == '@') {
person.push(make_pair(r, c));
}
if (building[r][c] == '*') {
fire.push(make_pair(r, c));
}
}
}
int time = 0;
while (int size = person.size()) {
// 불 번지고
int fireSize = fire.size();
while (fireSize--) {
int r = fire.front().first;
int c = fire.front().second;
fire.pop();
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (0 > nr || nr >= h || 0 > nc || nc >= w) continue;
if (building[nr][nc] == '.') {
building[nr][nc] = '*';
fire.push(make_pair(nr, nc));
}
}
}
// 사람 도망가고
int personSize = person.size();
while (personSize--) {
int r = person.front().first;
int c = person.front().second;
person.pop();
if (r == 0 || r == h - 1 || c == 0 || c == w - 1) return time + 1;
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (0 > nr || nr >= h || 0 > nc || nc >= w) continue;
if (!visited[nr][nc] && building[nr][nc] != '*' &&
building[nr][nc] != '#') {
visited[nr][nc] = true;
person.push(make_pair(nr, nc));
}
}
}
time++;
}
return -1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> tc;
while (tc--) {
memset(building, 0, sizeof(building));
memset(visited, 0, sizeof(visited));
cin >> w >> h;
for (int r = 0; r < h; r++) cin >> building[r];
int ans = bfs();
if (ans == -1)
cout << "IMPOSSIBLE\n";
else
cout << ans << "\n";
}
return 0;
}
- 1등 풀이
queue를 사용하지 않고 직접 큐를 구현하여 작성한 풀이, 빠르지만 작성하기 어렵다.
#include <iostream>
using namespace std;
class Point {
public:
short y;
short x;
};
char board__[1005 * 1005];
char* board_[1005];
char** board;
Point bQueue[1002001];
long long bQueueLeft;
long long bQueueRight;
long long bQueueCurrentRight;
long long d;
long long dy[4] = { -1, 0, 1, 0 };
long long dx[4] = { 0, 1, 0, -1 };
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
long long i, j;
board = board_ + 1;
for (i = 0; i < 1005; i++) {
board_[i] = board__ + 1 + i * 1005;
}
for (i = 0; i <= 1000; i++) {
board[i][-1] = 'E';
board[-1][i] = 'E';
}
long long t; cin >> t;
long long n, m;
long long turn;
for (long long ti = 0; ti < t; ti++) {
cin >> m >> n;
for (long long ni = 0; ni < n; ni++) {
cin >> board[ni];
}
bQueueLeft = 0;
bQueueRight = 0;
for (long long ni = 0; ni < n; ni++) {
for (long long mi = 0; mi < m; mi++) {
if (board[ni][mi] == '@') {
bQueue[bQueueRight].y = ni;
bQueue[bQueueRight].x = mi;
bQueueRight++;
}
}
}
for (long long ni = 0; ni < n; ni++) {
for (long long mi = 0; mi < m; mi++) {
if (board[ni][mi] == '*') {
bQueue[bQueueRight].y = ni;
bQueue[bQueueRight].x = mi;
bQueueRight++;
}
}
}
for (long long ni = 0; ni < n; ni++) {
board[ni][-1] = 'E';
board[ni][m] = 'E';
}
for (long long mi = 0; mi < m; mi++) {
board[-1][mi] = 'E';
board[n][mi] = 'E';
}
turn = 0;
while (bQueueLeft < bQueueRight) {
turn++;
bQueueCurrentRight = bQueueRight;
while (bQueueLeft < bQueueCurrentRight) {
long long y = bQueue[bQueueLeft].y;
long long x = bQueue[bQueueLeft].x;
if (board[y][x] == '*') {
for (d = 0; d < 4; d++) {
long long newY = y + dy[d];
long long newX = x + dx[d];
if (board[newY][newX] == '.') {
board[newY][newX] = '*';
bQueue[bQueueRight].y = newY;
bQueue[bQueueRight].x = newX;
bQueueRight++;
}
else if (board[newY][newX] == '@') {
board[newY][newX] = '*';
}
}
}
else if (board[y][x] == '@') {
for (d = 0; d < 4; d++) {
long long newY = y + dy[d];
long long newX = x + dx[d];
if (board[newY][newX] == '.') {
board[newY][newX] = '@';
bQueue[bQueueRight].y = newY;
bQueue[bQueueRight].x = newX;
bQueueRight++;
}
else if (board[newY][newX] == 'E') {
bQueueLeft = 99999999;
break;
}
}
}
bQueueLeft++;
}
}
if (bQueueLeft >= 99999999) {
cout << turn << '\n';
}
else {
cout << "IMPOSSIBLE\n";
}
}
}
댓글남기기