<Baekjoon> #14502 BFS_Laboratory c++
#14502 연구실
처음에 문제를 잘못 읽어서 바이러스가 바이러스 점을 기준으로 8방향으로 모두 퍼질 수 있다고 생각했고 이차원 배열을 call by value로 넘기려고 해서 큰 문제가 발생했었다..!
먼저 한 빈 공간을 기준으로 인접한 빈 공간부터 차례대로 3개씩 벽을 쌓아나가서 바이러스가 최소로 퍼질 수 있는 것을 구해야 한다.
map
생성 및 초기화vector<vector<int>> map(n, vector<int>(m)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> map[i][j];
(위에서 말한대로 처음에는
int map[MAX][MAX]
로 생성 했다가 파라미터로 넘길 때 문제가 발생해서 다시 바꿨다.)const int EMPTY = 0; const int WALL = 1; const int VIRUS = 2;
그리고 직관적으로 보이기 위해 각각의 이름을 지정해주었다.
- make wall
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == EMPTY) makeWall(map, i, j,1); } }
map
위의 모든Empty
공간에 대해서 조사를 해야하므로 이중 for문을 이용해 찾았고makeWall
함수에서 벽을 3개 만들 것이다.(여기서 원래 내가 입력받은
map
은 영구적으로 변경되면 안 되므로call by value
값으로 넘겨주어야 하는데, 이차원 벡터는 인자로 넘길 때call by reference
밖에 안 된다. 그래서vector
로 선언해야 한다. 그렇게 하기 싫으면 map을 복사해도 된다.)
makeWall
함수는 4개를 인자로 가지고 있다.
makeWall(vector<vector<int>> map, int y, int x, int cnt)
y,x는 현재map
위에서의 위치고,cnt
는 현재까지 만든 벽의 개수다. 만약 벽이 3개가 되면bfs
함수로 가서 바이러스가 퍼진 뒤Empty
공간의 개수를 구해서 최대값을 갱신한다.
- bfs
bfs(vector<vector<int>> &map)
bfs 함수 내 구현은 일반 bfs 함수의 구현과 크게 다른 점이 없다.
queue<pair <int, int>>q
를 만들고q
에는Virus
좌표를 넣어주고 인접한Empty
좌표에 대해pop, push
를 반복하며Virus
를 전파해준다.여기서 makeWall 함수에서 벽을 만들었던
map
을 그대로 가져와야 하기 때문에call by reference
로 가져왔다. 이 부분이 제일 헷갈렸던 부분이다.
전체코드
#include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; int n, m; const int EMPTY = 0; const int WALL = 1; const int VIRUS = 2; int result = 0; int dy[4] = { 0,0,1,-1 }; int dx[4] = { 1,-1, 0,0 }; void bfs(vector<vector<int>> &map) { queue <pair<int, int>> q; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == VIRUS) q.push(make_pair(i, j)); } } while (!q.empty()) { int cur_y = q.front().first; int cur_x = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx_y = cur_y + dy[i]; int nx_x = cur_x + dx[i]; if (nx_y<0 || nx_x<0 || nx_y>=n || nx_x>=m) continue; if (map[nx_y][nx_x] == EMPTY) { q.push(make_pair(nx_y, nx_x)); map[nx_y][nx_x] = VIRUS; } } } int cnt = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == EMPTY) cnt++; result = max(result, cnt); } void makeWall(vector<vector<int>> map, int y, int x, int cnt) { map[y][x] = WALL; if (cnt == 3) { bfs(map); return; } for (int i = y; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == EMPTY) makeWall(map, i, j, cnt + 1); } } } int main() { cin >> n >> m; vector<vector<int>> map(n, vector<int>(m)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> map[i][j]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == EMPTY) makeWall(map, i, j,1); } } cout << result << endl; return 0; }
Author And Source
이 문제에 관하여(<Baekjoon> #14502 BFS_Laboratory c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-14502-BFSLaboratory-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)