백준 5427번 풀이 c++ and java

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1 복사

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력 1 복사

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

 

 

bfs 문제이다.

불과 상근이가 동시에 움직이는걸 어떻게 코드로 표현해야할지 고민이 되었던 문제이다.

 

문제의 로직

1. 입출력을 모두 받아준다.

2. bfs를 돌린다.

3. startQ와 fireQ를 분리한다.

4. startQ에 첫 시작점을 넣어주고 while문으로 startQ가 empty하지 않을때 돌도록 설정한다.

5. 입력을 받으면서 불의 위치를 저장하고 그 위치를 하나씩 fireQ에 넣어준다.

6. 첫 fireQ의 사이즈만큼 변수에 할당 시키고 그 사이즈만큼 동서남북으로 불을 확장시켜준다.

7. 첫 startQ의 사이즈만큼 변수에 할당 시키고 그 사이즈만큼 동서남북으로 상근이를 움직여준다.

8. 만약에 상근이가 범위를 벗어나면 탈출에 성공했다고 판단하고 return을 해준다.

9. 만약에 상근이가 끝까지 범위를 벗어나지 못하면 탈출을 하지 못했다고 판단하고 impossible을 출력한다.

 

- c++

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

char graph[1000][1000];
bool visited[1000][1000];
int R, C;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };


void bfs(int r, int c, vector<pair<int,int>> fire){

    queue<pair<int,int>> startQ;
    queue<pair<int,int>> fireQ;

    int cnt = 0;

    startQ.push({r,c});

    for(int i = 0 ; i < fire.size(); i++){
        fireQ.push({fire[i].first,fire[i].second});
    }

    while(!startQ.empty()){
        cnt++;
        //fire먼저
        int fqSize = fireQ.size();
        for(int i = 0 ; i < fqSize; i++){
            int cr = fireQ.front().first;
            int cc = fireQ.front().second;
            fireQ.pop();
            for(int j = 0 ; j < 4; j++){
                int nr = cr + dir[j][0];
                int nc = cc + dir[j][1];
                if(nr >= 0 && nc >= 0 && nr < R && nc < C && graph[nr][nc] != '#'){
                    graph[nr][nc] = '#';
                    fireQ.push({nr,nc});
                }
            }
        }

        int sqSize = startQ.size();

        for(int i = 0 ; i < sqSize; i++){
            int cr = startQ.front().first;
            int cc = startQ.front().second;
            startQ.pop();
            for(int j = 0 ; j < 4; j++){
                int nr = cr + dir[j][0];
                int nc = cc + dir[j][1];

                if(nr<0 || nr>=R || nc >=C || nc<0){
                    cout << cnt << "\n";
                    return;
                }
                if(nr >= 0 && nc >= 0 && nr < R && nc < C && graph[nr][nc] != '#' && !visited[nr][nc]){
                    visited[nr][nc]=1;
                    startQ.push({nr,nc});
                }
            }

        }


    }

    cout << "IMPOSSIBLE" << "\n";




}



int main() {

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    int t;
    cin >> t;

    while(t--){

        cin >> C >> R;
        int r,c;
        vector<pair<int,int>> fire;

        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                cin >> graph[i][j];
                if(graph[i][j] == '*'){
                    fire.push_back({i,j});
                    graph[i][j]='#';
                }else if(graph[i][j]=='@'){
                    r = i;
                    c = j;
                }
            }
        }
        //solve
        bfs(r,c,fire);

        //reset
        memset(graph,' ',sizeof(graph));
        memset(visited,false,sizeof(visited));
    }
    return 0;
}

 

- java

import java.io.*;
import java.sql.Array;
import java.util.*;

class Point{
    int y;
    int x;
    Point(int y, int x){
        this.x = x;
        this.y = y;
    }
}

public class Main {


     static int R,C;
     static boolean [][] visited;
     static final int [][] di = {{0,1},{1,0},{-1,0},{0,-1}};
     static char [][] graph;

    static Queue<Point>startQ;
    static Queue<Point>fireQ;
    static class Point {
        int x;
        int y;

        Point(int y, int x){
            this.y= y;
            this.x = x;
        }
    }



    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());

        while (T-- > 0) {

            int r = 0, c = 0;
            st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            visited = new boolean[C][R];
            graph = new char[C+1][R+1];
            startQ = new LinkedList<Point>();
            fireQ = new LinkedList<Point>();

            ArrayList<Point> fire = new ArrayList<Point>();

            for (int i = 0; i < C; i++) {
                String s = br.readLine();
                for (int j = 0; j < R; j++) {
                    char ca = s.charAt(j);
                    graph[i][j]=ca;
                    if (ca == '@') {
                        r = j;
                        c = i;
                    } else if (ca == '*') {
                        fire.add(new Point(i, j));
                        graph[i][j]='#';
                    }
                }
            }

            bfs(r, c, fire);
        }
    }

    public static void bfs(int r, int c, ArrayList<Point> fire){


        int cnt = 0;

        startQ.add(new Point(c,r));

        for (int i = 0; i < fire.size() ; i++) {
//            System.out.println(fire.get(i).y + " " + fire.get(i).x + "fire!!!");
            fireQ.add(new Point (fire.get(i).y, fire.get(i).x));
        }

        while(!startQ.isEmpty()){
            int fireQSize = fireQ.size();
            cnt++;

            for(int i = 0 ; i < fireQSize; i++){
                Point poll = fireQ.poll();
                int cr = poll.x;
                int cc = poll.y;
                fireQ.peek();

//                System.out.println(cr+" " +cc);

                for(int j = 0 ; j < 4; j ++){
                    int nr = (cr + di[j][0]);
                    int nc = (cc + di[j][1]);
//                    System.out.println(nr + " " + nc);
                    if(nr >= 0 && nc >= 0 && nr < R && nc < C && (graph[nc][nr]=='.'||graph[nc][nr]=='@')){
//                        System.out.println("fire!!!!");

                        graph[nc][nr] = '#';
                        fireQ.offer(new Point(nc,nr));
                    }
                }
            }




            int startQSize = startQ.size();

            for(int i = 0 ; i < startQSize; i++){
                Point poll = startQ.poll();
                int cr = poll.x;
                int cc = poll.y;
                startQ.peek();

                for(int j = 0 ; j < 4; j ++){
                    int nr = cr + di[j][0];
                    int nc = cc + di[j][1];

                    if(nr<0 || nr>=R || nc >=C || nc<0){
                        System.out.println(cnt);
                        return;
                    }

                    if(nr>=0 && nc >=0 && nr<R && nc < C && graph[nc][nr]!='#'&&!visited[nc][nr]){
                        startQ.offer(new Point(nc,nr));
                        visited[nc][nr]=true;
                    }
                }
            }
        }


        System.out.println("IMPOSSIBLE");

    }



}