백준 5427 - 불(C++)

문제 링크입니다 https://www.acmicpc.net/problem/5427

5427번: 불

문제 조건

출력 예시

 

문제 접근 방법

1. 상근이의 위치와 불의 위치를 입력과 동시에 저장한다.

2. 저장한 불의 위치에서 상하좌우로 불을 붙인다.

3. 불을 피해 상윤이의 위치에세 상하좌우로 이동한다.

4. 2번과 3번이 끝난뒤의 각 정보들을 큐에 저장한다.

5. answer값에 따라서 출력한다.

6. 1~5번을 Test_case 만큼 반복한다.

 

문제 접근 방법 - 2번 + 3번 + 4번

int bfs() {
    int cnt = 0;
    queue<pair<int, int>> sang;
    queue<pair<int, int>> Fire;
    check[start.first][start.second] = 1;
    sang.push(start);
    for (int i = 0; i < fire.size(); i++) Fire.push(fire[i]);
    while (!sang.empty()) {
        int num_fire = Fire.size();
        int num_sang = sang.size();
        for (int k = 0; k < num_fire; k++) {
            int fire_x = Fire.front().first;
            int fire_y = Fire.front().second;
            Fire.pop();
            for (int i = 0; i < 4; i++) {
                int xx = fire_x + dx[i];
                int yy = fire_y + dy[i];
                if (xx >= 1 && yy >= 1 && xx <= h && yy <= w) {
                    if (building[xx][yy] == '.') {
                        building[xx][yy] = '*';
                        Fire.push({ xx,yy });
                    }
                }
            }
        }
        for (int k = 0; k < num_sang; k++) {
            int x1 = sang.front().first;
            int y1 = sang.front().second;
            sang.pop();
            if (x1 == 1 || y1 == 1 || x1 == h || y1 == w) {
                return cnt + 1;
            }
            for (int i = 0; i < 4; i++) {
                int xx = x1 + dx[i];
                int yy = y1 + dy[i];
                if (xx >= 1 && yy >= 1 && xx <= h && yy <= w) {
                    if (check[xx][yy] == 0 && building[xx][yy] == '.') {
                        check[xx][yy] = 1;
                        sang.push(make_pair(xx, yy));
                    }
                }
            }
        }
        cnt++;
    }
    return -1;
}

불의 이동과 상근이의 이동이 동시에 있는 BFS코드입니다.

상근이는 불이 붙을 예정인 곳으로는 이동하지 못합니다. -> 불을 먼저 붙인뒤, 불이 없는 곳으로는 이동할 수 있다!

따라서 불을 먼저 붙인 뒤, 상근이를 이동했습니다.

"불을 붙인다 -> 상근이를 이동시킨다"의 과정이 반복되야하기에, 들어있는 큐의 갯수만큼만 각각 반복해줍니다.

 

1. 불의 경우

 불은 벽을 제외하고는 모든 곳에 이동할 수 있습니다. 따라서 x,y 좌표의 범위에 속할 때, 해당 좌표가 벽이 아니라면 이동해줍니다.

2. 상근이의 경우

상근이는 자신이 방문하지 않은 빈공간을 제외하고는 이동할 수 없습니다. 따라서 x,y 좌표의 범위에 속할 때, 이전에 방문하지 않았고, 빈공간이라면 이동해줍니다.

상근이가 탈출할 수 있는 조건은 모서리에 위치한 빈 공간일때 입니다. 이 경우에는 이동 횟수를 저장한 뒤, 탐색을 종료합니다.   

 

문제 접근 방법 - 5번

void solve() {
    int answer = bfs();
    if (answer == -1) cout << "IMPOSSIBLE" << "\n";
    else cout << answer << "\n";
}

answer에 BFS의 return 값을 저장해 answer 값에 따라서 출력해줍니다.

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

int test_case;
int w, h;
char building[1001][10001];
int check[1001][1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
pair<int, int> start;
vector<pair<int, int>> fire;


int bfs() {
    int cnt = 0;
    queue<pair<int, int>> sang;
    queue<pair<int, int>> Fire;
    check[start.first][start.second] = 1;
    sang.push(start);
    for (int i = 0; i < fire.size(); i++) Fire.push(fire[i]);
    while (!sang.empty()) {
        int num_fire = Fire.size();
        int num_sang = sang.size();
        for (int k = 0; k < num_fire; k++) {
            int fire_x = Fire.front().first;
            int fire_y = Fire.front().second;
            Fire.pop();
            for (int i = 0; i < 4; i++) {
                int xx = fire_x + dx[i];
                int yy = fire_y + dy[i];
                if (xx >= 1 && yy >= 1 && xx <= h && yy <= w) {
                    if (building[xx][yy] == '.') {
                        building[xx][yy] = '*';
                        Fire.push({ xx,yy });
                    }
                }
            }
        }
        for (int k = 0; k < num_sang; k++) {
            int x1 = sang.front().first;
            int y1 = sang.front().second;
            sang.pop();
            if (x1 == 1 || y1 == 1 || x1 == h || y1 == w) {
                return cnt + 1;
            }
            for (int i = 0; i < 4; i++) {
                int xx = x1 + dx[i];
                int yy = y1 + dy[i];
                if (xx >= 1 && yy >= 1 && xx <= h && yy <= w) {
                    if (check[xx][yy] == 0 && building[xx][yy] == '.') {
                        check[xx][yy] = 1;
                        sang.push(make_pair(xx, yy));
                    }
                }
            }
        }
        cnt++;
    }
    return -1;
}

void solve() {
    int answer = bfs();
    if (answer == -1) cout << "IMPOSSIBLE" << "\n";
    else cout << answer << "\n";
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> test_case;
    for (int k = 0; k < test_case; k++) {
        memset(check, 0, sizeof(check));
        fire.clear();
        cin >> w >> h;
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                cin >> building[i][j];
                if (building[i][j] == '@') {
                    start.first = i;
                    start.second = j;
                }
                if (building[i][j] == '*') {
                    fire.push_back(make_pair(i, j));
                }
            }
        }
        solve();
    }

    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!