어쩌다가 이문제 풀어보고싶어서 나도 도전해봤다. 3일쨰보고 있는데 아직 60%만 이해한거같음 새로알게된건,
벡터의 사용법과 언제쓰는지, Range - based for loop (반복문안에서 내용수정) , 배열의 행과열에대해서 다시공부할 수 있었다. 벡터는 (행,열) 순서, y는 행 x는 열
수학에서의 좌표 와 반대되는 위치에 놓임 y가 -이면 위로올라가고 + 이면 내려감
dfs 자료구조에대해 작년에 이론만 공부하고 문제풀었는데 구현하면서 응용하는거보니까 쉬워보이면서도 어렵다.
백준 골드는 내년에 푸는걸로 해야겠다.. 아래는 공부한내용
★☆★☆ 의사코드와 코드 순서 ★☆★☆
wall벡터 ( 0의 좌표를 저장)
virus 벡터 ( 2의 좌표를 저장)
연구소의 크기 n,m , 최대 안전영역 = ans
최대크기의 안전영역은 모든 경우의 수를 계산해야한다.
-바이러스가 상하좌우로 쭉 퍼질때
1.연구소 크기의 map 2차원 배열 - 연구소의 전체크기를 벡터로나타내는 배열 ( 0,1,2 중에 하나를 저장)
연구소 크기의 visited 2차원 배열 - 연구소의 크기만큼에 경우의수 바이러스 지점을 나타내는 배열 ( 바이러스칸저장(2) )
------메인함수-----
1. 연구소 크기만큼의 2중반복문을 선언 , 입력이 0 이면 wall벡터에저장 , 입력이 2 이면 virus 벡터에 저장
2.바이러스가 얼만큼 퍼지는지에대한 경우의수 영역 계산 ( int length = wall.size(),
3.벽을 세울 수 있는 공간을 탐색 ( 3중반복문) ijk 모든 경우의수를 탐색 , ijk 의 범위는 서로 달라야한다( 벽을 중복해서 세울수없다.)
4. 벽을 세울 수 있는 최대안전영역 ans = max(ans,count()) max 함수를 이용해서 바이러스가 퍼지는영역인 count()함수와 비교후 최대크기를 ans에 저장
현재까지 구한안전영역의 크기와 현재 경우의 안전영역의 크기를 비교해서 , 더 큰 안전영역을 찾음
5. ans 값을 선정하고나서 , 벽을 세웠던위치를 다시 빈칸으로 돌려놓는다.(다른 경우의 수 탐색시 영향 x )
-------------메인함수----------
6.바이러스가 퍼지는 지역을 찾는 dfs 함수
void dfs ( int row, int col) {
for( i <4 상우하좌 에 대한 검사
int ny = row +dy[i] 방향이동 배열에 현재의 위치를 저장해서 다음의위치 (ny) 를 계산
int nx = col + dx[i] 방향이동 배열에 현재의 위치를 저장해서 다음의위치 (nx) 를 계산
7. 연구소에남은 빈칸의 개수를구하는 함수 ( 벽을 세울 수 있는 최대안전영역 값을 구하기위해 꼭필요)
int count(){ //빈칸의 개수를 구할때는 벽을 세우고나서 다시뻈기때문에 다시 0 으로 초기화 해줘야함
memset(visited, 0 , sizeof(visited)) // 방문한지역 모두0 으로 초기화
for(auto &v : virus) { 바이러스가 이미 퍼진 지역은 방문 필요 x , 방문했다고1 로 체크 후 다시 해당지점에서 dfs
visited,[v.first][v.second] =1; //
dfs(v.first,v.second) // 해당지점에서 다시 dfs
}
8. map 배열에 모든칸을 순회하면서 , 빈칸인데 방문하지않은칸 의 개수를 ret 에 더해줌
for for i<n j<m
= map 이0 visited 가 0일때 ret++
#include <iostream>
#include <vector> //벡터 함수
#include <algorithm> //sort 함수 ,최대값을 찾기 위한 헤더 파일
#include <cstring> // memset 함수를 사용하기 위한 헤더 파일
using namespace std;
const int dx[] = { 0, 1, 0, -1 }; // x 방향 이동을 위한 배열★★
//dx 배열은 이동 방향을 쉽게 표현할 수 있도록 0부터 3까지 순서대로 상, 우, 하, 좌 순서(시계방향)로 선언
const int dy[] = { -1, 0, 1, 0 }; // y 방향 이동을 위한 배열
//음수부분은 위방향(0번인덱스)
//양수부분은 아래방향 (2번인덱스)
int map[8][8], visited[8][8]; // 연구소의 정보와 방문 여부를 저장하는 배열★★
// map 은 0,1,2 중에 하나를 저장함
//visited 는 방문되었는지의 여부를 저장
vector<pair<int, int>> wall;
// map 배열에서 벽을 세울 수 있는 0(빈칸)으로 되어있는 위치(좌표)를 wall 벡터에저장
vector<pair<int, int>> virus;
// map배열에서 값이2인 위치는 바이러스칸이고 해당위치(좌표)를 virus 벡터에 저장
pair<int, int>는 두 개의 정수를 저장하는 객체로, 첫 번째 원소는 first, 두 번째 원소는 second라는 이름으로 접근
pair는 두 개의 값이 서로 관련이 있는 경우 사용
예를 들어, 2차원 평면 상의 좌표나 두 개의 값을 한 쌍으로 반환해야 하는 경우 등에서 유용하게 사용
int n, m; // 연구소의 크기
int ans; // 바이러스가 퍼지지 않은 지역의 최대 개수(안전영역의 크기 )
void dfs(int row, int col) { // DFS를 이용해 바이러스가 퍼지는 지역을 찾는 함수★★
for (int i = 0; i < 4; ++i) { // 상우하좌 4방향에 대해 검사
int ny = row + dy[i]; // 다음이동할 위치 (행)
int nx = col + dx[i]; // 다음이동할 위치 (열)
row와 col 은 현재위치의 행과 열을 나타냄
ny 와 nx는 row 와 col(현재위치) 에 따른 다음 위치를 나타내는 변수이다.
dy[i] dx[i]는 상하좌우로 이동을 하기위한 값을 저장중 i 변수로 방향을 참조하게됨
ny 와 nx 가 연속적으로 바뀌면서 dfs 함수가 전체 연구소를 탐색하게됨
연구소의 범위를 벗어나거나 이미 방문한 지역이면 건너뛰는 코드 ★★
if (ny < 0 || nx < 0 || ny >= n || nx >= m) // 범위를 벗어날때의 코드
continue;
if (visited[ny][nx]) // 이미 방문한지역이면
continue;
if (map[ny][nx] == 1) // 이미 방문한지역이면, [ny][nx] 가 1일때
continue;
visited[ny][nx] = 1; // ny와 nx 에 1을 대입해서 방문처리함
dfs(ny, nx); // 다음 이동할 위치에대해 재귀호출
}
}
int count() {//바이러스가 퍼진후, 연구소내에 남아있는 빈칸(0)의 개수를 구하는 함수★★
memset(visited, 0, sizeof(visited));
/*모든 지점을 방문하지 않은 상태로 초기화하기 위해 visited 배열을 0으로 초기화
memset은 C++에서 메모리 블록(연속된 메모리영역) 을 지정한 값으로 설정하는 함수
함수의 인자로는 메모리 블록의 시작 위치, 설정하고자 하는 값, 그리고 메모리 블록의 크기를 입력
이 때 설정하고자 하는 값은 0으로 초기화하고자 할 때는 0으로 지정
즉, memset( 배열이름(포인터),초기화할 값(채울 값), 연속된메모리영역의크기)
보통 0 또는 -1 을 많이 사용함
이 배열을 초기화하지 않으면 이전에 다른 상황에서 방문한 적이 있는 칸이 방문한 적이 없는 것으로 처리되어 잘못된 결과가 나올 수 있기 때문에,
이를 방지하기 위해 memset을 사용하여 visited 배열을 0으로 초기화*/
/*Range - based for loop 기능 = 컨테이너에 저장된 모든 요소를 차례대로 가져와서 사용
*
for (변수의 형식& 변수 : 컨테이너) {
// 코드
}
변수 = 콜론 오른쪽에있는 '컨테이너' 의 각 요소를 차례대로 가리키는 변수
변수의 형식 == 컨테이너 요소의 형식(변수의 형식과 컨테이너 요소의 형식은 서로 일치해야한다.) 그러므로 auto & 키워드사용
auto & 키워드(참조자)의 의미 : auto & 사용함으로써 요소의 형식을 자동으로 맞추게끔 결정가능
auto & 키워드로 컨테이너의 요소를 참조하는 레퍼런스를 만듬->반복문안에서 변수 수정이가능해짐 */
for (auto& v : virus) {//바이러스가 퍼져있는 지점을 방문했다고 체크하기 위해 visited 배열의 특정 위치를 1로 변경하는 코드★★
visited[v.first][v.second] = 1; // 해당 바이러스가 위치한 곳을 체크해서 1로 변경
// 2차원 배열에서 행과 열 인덱스를 사용하여 특정 위치를 지정하기 위해 사용
dfs(v.first, v.second); //v.first와 v.second는 pair 타입에서 첫 번째 요소와 두 번째 요소를 의미
//dfs(v.first, v.second)는 바이러스가 위치한 행과 열 값을 매개변수로 해서 dfs 함수 호출
}
수행과정:
for문 안에서 각각의 바이러스 위치에서부터 DFS 탐색을 수행
virus 라는 백터에 바이러스의 위치정보를저장, 순회하면서 각각의 위치를 바이러스 지점으로 간주하고
visited 배열에서 해당위치를 체크해줌,즉, "visited" 배열에서 값이 1이면 바이러스가 퍼져있는 지점,0이면 바이러스가 퍼져있지 않은 지점
이렇게 체크된 바이러스의 위치를 시작점으로 하여 DFS 탐색을 수행
그리고 바이러스의 위치를 시작점으로 해서 DFS 탐색을 수행하여, 바이러스가 퍼져있는 지점을 모두 방문했다고 체크
int ret = 0; // 빈칸인동시에, 방문하지않은칸의 개수++
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (map[i][j] == 0 && visited[i][j] == 0) //0인 부분을 체크하는 코드★★
++ret;
}
}
map 배열의 모든 칸을 순회하면서,
빈 칸인데 방문하지 않은 칸(즉, 바이러스가 퍼져있지 않은 칸)의 개수를 세어 ret에 더줌
map배열이 0일때(빈칸), visited 배열이 0 일때(방문하지않은칸)
return ret;
}
int main() { //입력받은 연구소의 크기와 빈 칸과 바이러스가 위치한 곳을 파악할 수 있다.★★
// 3 ≤ N, M ≤ 8
cin >> n >> m; //연구소의 정보 n,m 입력받음
// 연구소 정보 입력 // n*m 크기의 연구소 입력받음
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> map[i][j];
if (map[i][j] == 0) wall.push_back({ i, j }); //입력받은 값이 0(빈칸) 이라면
//wall 백터에 해당칸의 위치를 더함
if (map[i][j] == 2) virus.push_back({ i, j });//만약 입력받은 칸이 바이러스(2)라면,
//바이러스가 있는 위치를 virus 벡터에 더함
}
}
WALL.SIZE() 로 반복문의 실행 횟수를 줄임
int length = wall.size(); //벽을 세울 수 있는 모든 경우의 수를 찾고
각 경우마다 바이러스가 퍼지는 영역을 계산 ,
가장 큰영역을 찾는 코드
, wall 벡터에는 빈 칸인 위치들의 좌표가 저장
for (int i = 0; i < length; ++i) {3중 for 루프를 사용하여 벽을 세울 수 있는 모든 경우의 수를 탐색
for (int j = 0; j < i; ++j) { // i, j, k는 서로 다른 위치를 가리키는 인덱스(3개의벽)
for (int k = 0; k < j; ++k) {
map[wall[i].first][wall[i].second] = 1;
map[wall[j].first][wall[j].second] = 1;
map[wall[k].first][wall[k].second] = 1;
바이러스가 퍼지는 영역을 계산하기 위해 count() 함수를 호출★★
count() 함수는 BFS를 사용하여 바이러스가 퍼지는 영역의 크기를 계산
각 경우마다 계산한 바이러스가 퍼지는 영역의 크기를 비교하여,
그 중에서 가장 큰 값을 ans 변수에 저장
ans = max(ans, count());//세 개의 벽을 세운 후 , 세운 벽을 기준으로
map[wall[i].first][wall[i].second] = 0; //마지막으로, 벽을 세웠던 위치를 다시 빈 칸으로 돌려놓는다. ★★
//벽을 세운 후에는 다시 빈 칸으로 만들어야 다른 경우의 수를 탐색할 때 영향을 주지 않는다.
map[wall[j].first][wall[j].second] = 0;
map[wall[k].first][wall[k].second] = 0;
}
}
}
cout << ans << '\n';
}