[BOJ 4179] 불! (C++)

www.acmicpc.net/problem/4179

4179번: 불!

불! 문제

 

구현 방법

이 문제는 BFS(Breadth First Search)를 활용한 문제입니다.

기본적인 BFS문제는 Flood Fill 같이 하나의 탐색점을 두고 풀 수 있는데, 이 문제는 불, 지훈이 각각 두 번의 BFS로직을 구현해야 합니다.

 

BFS, 즉 너비 우선 탐색은 다음과 같은 알고리즘을 따릅니다.

• 시작하는칸을 큐에 넣고 방문했다는 표시 남김
• 큐의 front를 꺼내고 해당 원소의 상, 하, 좌, 우 탐색
• 상하좌우 중 해당 칸을 이미 방문했다면 종료, 처음으로 방문하면 방문 표시 남기고 큐에 삽입.
• 큐가 빌 때 까지 반복

 

변수 설명

board[1001]	미로 정보 입력 받을 배열 (1001개의 string 형 문자열 받을것이니 char형의 2차원 배열과 동일한 개념)
dist1[1001][1001]	불에 대한 BFS수행해 거리 표시할 배열
dist2[1001][1001]	지훈이에 대한 BSF 수행해 거리 표시할 배열

dist1과 dist2배열은 모두 -1로 초기화해주고, 불과 지훈이의 위치에는 0, 방문하며 (이전 거리+1)을 대입해주며 불과 지훈이의 이동거리에 대한 값들을 모두 넣어 줍니다.

 

지훈이에 대한 BFS을 수행할때 범위 밖으로 나가면 탈출하니, 거리를 출력해주고 프로그램을 종료합니다.

 

지훈이에 대한 BFS를 할 때는 이동하려는 칸의 dist1, 즉 불이 해당 칸까지 가는 거리가 지훈이보다 짧으면 지훈이는 해당 칸으로 이동 못한다는 걸 추가해줘야 합니다.

 

위 로직은 다음과 같이 구현했습니다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

string board[1001];
int dist1[1001][1001]; //불 거리
int dist2[1001][1001]; //지훈이 거리
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    queue<pair<int, int>> Q1; //불 큐
    queue<pair<int, int>> Q2; //지훈이 큐
	
    //미로 판 행,렬 입력 받고 불이 이동할 거리, 지훈이가 이동할 거리 2차원 배열 -1로 초기화
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        fill(dist1[i], dist1[i] + m , -1);
        fill(dist2[i], dist2[i] + m , -1);
    }
	
    //판 입력 받기
    for(int i=0;i<n;i++)
        cin >> board[i];
	
    //판 전체를 탐색하며 dist1에는 불 위치 표시하고 불 큐에 넣음
    // dist 2에는 지훈이 위치 표시하고 지훈이 큐에 넣음
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(board[i][j] == 'F') {
                dist1[i][j] = 0;
                Q1.push({i,j});
            }
            if(board[i][j] == 'J') {
                dist2[i][j] = 0;
                Q2.push({i,j});
            }
        }
    }

    //불에 대한 BFS
    while(!Q1.empty()) {
        auto cur = Q1.front(); Q1.pop();
		
        //상하좌우 탐색
        for(int dir=0;dir<4;dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
			
            //불은 범위 밖으로 못나간다
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            //방문했던 위치는 거리가 -1이 아닐것, 벽이면 방문 못함
            if(board[nx][ny] == '#' || dist1[nx][ny] >=0) continue;
			
            //새로운 장소 까지의 거리 지정해줘서 방문했다고 체크
            //큐에 넣어줌
            dist1[nx][ny] = dist1[cur.first][cur.second] + 1;
            Q1.push({nx,ny});
        }
    }

    //지훈이에 대한 BFS
    while(!Q2.empty()) {
        auto cur = Q2.front(); Q2.pop();
		
        //상하좌우 탐색
        for(int dir=0;dir<4;dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
			
            //지훈이의 경우 배열의 범위에서 나가면 탈출했다는 뜻
            //탈출할때 까지의 거리 출력하고 프로그램 종료
            if(nx<0||nx>=n||ny<0||ny>=m) {
                cout << dist2[cur.first][cur.second] + 1;
                return 0;
            }
            //방문했던 위치는 거리가 -1이 아닐것, 벽이면 방문 못함
            if(board[nx][ny] == '#' || dist2[nx][ny] >= 0) continue;
            //불이 지훈이보다 빨리도착하는 경우 추가
            if(dist1[nx][ny] != -1 && dist1[nx][ny] <= dist2[cur.first][cur.second]+1) continue;
			
            //새로운 장소 까지의 거리 지정해줘서 방문했다고 체크
            //큐에 넣어줌
            dist2[nx][ny] = dist2[cur.first][cur.second] + 1;
            Q2.push({nx,ny});

        }
    }
    //만약 탈출 못하면 프로그램 종료 못하고 여기까지 오게됨 IMPOSSIBLE출력
    cout << "IMPOSSIBLE";
}