[정올] 저글링 방사능 오염

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358&sca=3040 

JUNGOL

BFS를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

저글링에 방사능 오염 공격을 가하게 되는데, 방사능 오염공격을 맞은 저글링은 3초후 죽습니다. 추가적으로 1초마다 오염된 저글링 바로 옆의 저글링에게 오염이 전이됩니다. 이 때, 저글링의 위치와, 공격받는 저글링이 주어질 때, 총 몇초만에 죽을 수 있는 저글링들이 모두 없어지는지를 구해야 합니다. 

 

추가적으로, 죽지않고 남아 있는 저글링의 수도 출력해야 합니다.

 

<Solution>

BFS를 이용해야 합니다. queue를 만들고, 처음 방사능 공격을 받는 저글링을 넣어줍니다. 

이 때, r,c,time 이렇게 3개의 value를 넣게 되는데 

 

r,c 는 상태전이를 위해 필요하고, time은 정답을 구하기 위해 필요합니다. 

이렇게 queue에 넣어주고, 상태전이를 시켜주어 큐가 빌때까지 이 과정을 한 이후, 시간을 구해주면 됩니다.

 

저글링의 수는 처음에 미리 세어두고, queue에 저글링을 넣을 때 마다 하나씩 빼주면 구할 수 있습니다. (이 방식 말고도 마지막에 세어주는 방식을 이용하여도 됩니다.)

 

실제 구현은 아래와 같습니다. 

(아래 코드도 맞는데 정올 사이트에선 오류가 나서 추가적으로 수정하여 하나 더 첨부합니다.)

#include <iostream>
#include <queue>
 
using namespace std;
 
#define MAXN (100)
int W, H;//지도의 가로 세로 크기
char map[MAXN+10][MAXN+10];//지도 정보('1':저글링, '0':빈곳)
int sw, sh;//시작위치 가로 세로 좌표
int juggling;
 
int d_row[] = {1, -1, 0, 0};
int d_col[] = {0, 0, 1, -1};
 
struct tmp{
    int r, c, time;
};
 
void InputData(){
    cin >> W >> H;
    for (int i=1; i<=H; i++){
        cin >> &map[i][1];
    }
    for(int i = 1; i<=H; i++){
        for(int j = 1; j<=W; j++){
            if(map[i][j] == '1') juggling++;
        }
    }
    cin >> sw >> sh;
}
 
int solution(){
    int time;
 
    queue <struct tmp> q;
    q.push((struct tmp){sh, sw, 3});
    map[sh][sw] = '0';
    juggling--;
    while(!q.empty()){
        struct tmp e = q.front();
        q.pop();
        time = e.time;
 
        for(int i = 0; i<4; i++){
            if(map[e.r+d_row[i]][e.c+d_col[i]] == '1'){
                map[e.r+d_row[i]][e.c+d_col[i]] = '0';
                juggling--;
                q.push((struct tmp){e.r+d_row[i],e.c+d_col[i],e.time+1});
            }
        }
 
 
    }
 
    return time;
 
}
 
int main(){
    InputData();//입력 받는 부분
 
    //여기서부터 작성
 
    cout << solution() << endl;
    cout << juggling << endl;
 
 
    return 0;
}

[정올 사이트용 code]

#include <stdio.h>
#include <iostream>
#include <queue>

#define MAXN (100)

using namespace std;
 
int W, H;//지도의 가로 세로 크기
char map[MAXN+10][MAXN+10];//지도 정보('1':저글링, '0':빈곳)
int sw, sh;//시작위치 가로 세로 좌표
int juggling;
 
int d_row[] = {1, -1, 0, 0};
int d_col[] = {0, 0, 1, -1};

struct tmp{
    int r, c, time;
};

void InputData(void){
    scanf("%d %d", &W, &H);
    for (int i=1; i<=H; i++){
        scanf("%s", &map[i][1]);
    }
    for(int i = 1; i<=H; i++){
        for(int j = 1; j<=W; j++){
            if(map[i][j] == '1') juggling++;
        }
    }
    scanf("%d %d", &sw, &sh);
}
 
int solution(){
    int time;
 
    queue <struct tmp> q;
    q.push((struct tmp){sh, sw, 3});
    map[sh][sw] = '0';
    juggling--;
    while(!q.empty()){
        struct tmp e = q.front();
        q.pop();
        time = e.time;
 
        for(int i = 0; i<4; i++){
            if(map[e.r+d_row[i]][e.c+d_col[i]] == '1'){
                map[e.r+d_row[i]][e.c+d_col[i]] = '0';
                juggling--;
                q.push((struct tmp){e.r+d_row[i],e.c+d_col[i],e.time+1});
            }
        }
 
 
    }
 
    return time;
 
}
 
int main(void){
    InputData();//입력 받는 부분
 
    //여기서부터 작성
 
    cout << solution() << endl;
    cout << juggling << endl;
 
 
    return 0;
}