백준 4179 - 불!(C++)

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

4179번: 불!

이 문제와 동일한 문제였습니다 https://junseok.tistory.com/63 

백준 5427 - 불(C++)

문제 조건

출력 예시

 

문제 접근 방법

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

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

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

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

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

 

 

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

int bfs() {
    check[start.first][start.second] = 1;
    q.push({ start.first, start.second });
    for (int i = 0; i < fire.size(); i++) Fire.push(fire[i]);
    while (!q.empty()) {
        int fire_size = Fire.size();
        int q_size = q.size();
        for (int i = 0; i < fire_size; i++) {
            int x = Fire.front().first;
            int y = Fire.front().second;
            Fire.pop();
            for (int j = 0; j < 4; j++) {
                int xx = x + dx[j];
                int yy = y + dy[j];
                if (xx >= 1 && yy >= 1 && xx <= R && yy <= C) {
                    if (map[xx][yy] == '.' || map[xx][yy] == 'J') {
                        map[xx][yy] = 'F';
                        Fire.push(make_pair(xx, yy));
                    }
                }
            }
        }
        for (int i = 0; i < q_size; i++ ) {
            int x = q.front().x;
            int y = q.front().y;
            int cnt = q.front().cnt;
            if (x == 1 || y == 1 || x == R || y == C) {
                return cnt+1;
            }
            q.pop();
            for (int j = 0; j < 4; j++) {
                int xx = x + dx[j];
                int yy = y + dy[j];
                if (xx >= 1 && yy >= 1 && xx <= R && yy <= C) {
                    if (map[xx][yy] == '.' && check[xx][yy] == 0) {
                        check[xx][yy] = 1;
                        q.push({ xx,yy,cnt + 1 });
                    }
                }
            }
        }
    }
    return -1;
}

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

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

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

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

 

1. 불의 경우

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

2. 지훈이의 경우

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

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

 

문제 접근 방법 - 5번

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

answer의 값에 따라서 출력을 다르게 했습니다.

 

 

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

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

int R, C;
char map[1001][1001];
int check[1001][1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
typedef struct qu{
    int x;
    int y;
    int cnt;
}qu;
queue<qu> q;
queue<pair<int, int>> Fire;
vector<pair<int, int>>fire;
pair<int, int> start;

int bfs() {
    check[start.first][start.second] = 1;
    q.push({ start.first, start.second });
    for (int i = 0; i < fire.size(); i++) Fire.push(fire[i]);
    while (!q.empty()) {
        int fire_size = Fire.size();
        int q_size = q.size();
        for (int i = 0; i < fire_size; i++) {
            int x = Fire.front().first;
            int y = Fire.front().second;
            Fire.pop();
            for (int j = 0; j < 4; j++) {
                int xx = x + dx[j];
                int yy = y + dy[j];
                if (xx >= 1 && yy >= 1 && xx <= R && yy <= C) {
                    if (map[xx][yy] == '.' || map[xx][yy] == 'J') {
                        map[xx][yy] = 'F';
                        Fire.push(make_pair(xx, yy));
                    }
                }
            }
        }
        for (int i = 0; i < q_size; i++ ) {
            int x = q.front().x;
            int y = q.front().y;
            int cnt = q.front().cnt;
            if (x == 1 || y == 1 || x == R || y == C) {
                return cnt+1;
            }
            q.pop();
            for (int j = 0; j < 4; j++) {
                int xx = x + dx[j];
                int yy = y + dy[j];
                if (xx >= 1 && yy >= 1 && xx <= R && yy <= C) {
                    if (map[xx][yy] == '.' && check[xx][yy] == 0) {
                        check[xx][yy] = 1;
                        q.push({ xx,yy,cnt + 1 });
                    }
                }
            }
        }
    }
    return -1;
}

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

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> R >> C;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'J') {
                start.first = i;
                start.second = j;
            }
            if (map[i][j] == 'F') {
                fire.push_back(make_pair(i, j));
            }
        }
    }
    solve();
    return 0;
}

 

 

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