Queue를 이용한 일관된 framework로 쉬운 BFS(Breadth First Search)문제를 풀어보자

이번학기 수강중인 멀티미디어 프로그래밍 수업에서 BFS 유형의 문제를 이것저것 풀고 있습니다. 교수님께서 queue를 사용하면 된다고 하셔서 queue를 썼더니 놀랍게도 모든 문제가 쉽게 풀려서, 내친김에 대부분의 BFS 문제를 전부 일관된 Framework로 해결할 수 있도록 정리를 해두려 합니다. (컴공과 학생들에게는 너무나도 당연한 건데, 늦게라도 이런걸 알아서 다행입니다) 아래 두 문제에 대해 적용해보았습니다. [화염에서 탈출](http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1839&sca=3040) [저글링 감염](http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=362&sca=3040) ```cpp 1. 입력 파싱 -> 변수 초기화 (변수: 배열 또는 그래프 형태의 지도, 위치정보를 가지는 instance) 2. queue 초기화 (맨 처음 출발해야 하는 worker들을 queue에 넣어줍니다) 3. while(!queue.empty()) { 4. worker = queue.front(); queue.pop(); n. 프로세스 #1 with worker n+1. 프로세스 #2 with worker ... } -2. 성공 여부 확인 -1. 출력 ``` '화염에서 탈출'문제에서 실제로 사용한 코드입니다. ```cpp #include <iostream> #include <queue> #include <vector> #include <string> struct Object { int x,y; int id; // also time it takes Object(int x=0, int y=0, int id=0):x(x),y(y),id(id){} }; void initialize_objects(int (&forest)[50][50], Object& man, std::vector<Object>& fires, Object& home); void initialize_queue(std::queue<Object>& obj_queue, Object& man, std::vector<Object>& fires); void process_fire(int (&forest)[50][50], std::queue<Object>& obj_queue, Object& fire, int (&move)[4][2]); void process_man(int (&forest)[50][50], std::queue<Object>& obj_queue, Object& man, int (&move)[4][2]); void check_success(int& is_success, int (&forest)[50][50], Object& home); // tools bool is_valid(Object& obj, int (&forest)[50][50]); int main(void) { int forest[50][50] = {-99}; std::queue<Object> obj_queue; Object man, home; std::vector<Object> fires; int move[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; initialize_objects(forest, man, fires, home); initialize_queue(obj_queue, man, fires); while(!obj_queue.empty()) { Object obj = obj_queue.front(); obj_queue.pop(); //std::cout << "id: " << obj.id << std::endl; //std::cout << obj.y << " " << obj.x << std::endl; if (obj.id == -2) process_fire(forest, obj_queue, obj, move); else process_man(forest, obj_queue, obj, move); } // int is_success = forest[home.y][home.x]; if(is_success == -3) std::cout << "impossible" << std::endl; else std::cout << is_success << std::endl; return 0; } void initialize_objects(int (&forest)[50][50], Object& man, std::vector<Object>& fires, Object& home) { int R,C; std::cin >> R >> C; std::string buffer; for (int irow=0; irow < R; irow++) { std::cin >> buffer; for (int icol=0; icol < C; icol++) { if(buffer[icol] == 'S') // man { forest[irow][icol] = 0; man = Object(icol,irow,0); } else if(buffer[icol] == '*') // fire { forest[irow][icol] = -2; fires.push_back(Object(icol,irow,-2)); } else if(buffer[icol] == 'X') // stone { forest[irow][icol] = -2; } else if(buffer[icol] == 'D') // home { forest[irow][icol] = -3; home = Object(icol,irow,0); } else if(buffer[icol] == '.') // grass { forest[irow][icol] = -1; } else { std::cout << "Error in setting forest" << std::endl; } } } } void initialize_queue(std::queue<Object>& obj_queue, Object& man, std::vector<Object>& fires) { // care order! (fire , man) (O) (man, fire) (X) for (int i=0; i < fires.size(); i++) obj_queue.push(fires[i]); obj_queue.push(man); } void process_fire(int (&forest)[50][50], std::queue<Object>& obj_queue, Object& fire, int (&move)[4][2]) { for (int i = 0; i < 4; i++) { Object cfire(fire.x + move[i][0], fire.y + move[i][1], -2); if (cfire.x >= 0 && cfire.y >= 0 && forest[cfire.y][cfire.x] == -1) { forest[cfire.y][cfire.x] = cfire.id; obj_queue.push(cfire); } } } void process_man(int (&forest)[50][50], std::queue<Object>& obj_queue, Object& man, int (&move)[4][2]) { for (int i = 0; i < 4; i++) { Object cman(man.x + move[i][0], man.y + move[i][1], man.id+1); if (cman.x >= 0 && cman.y >= 0 && (forest[cman.y][cman.x] == -1 || forest[cman.y][cman.x] == -3)) { forest[cman.y][cman.x] = cman.id; obj_queue.push(cman); } } } ```