내가 백준 문제를 풀면서 느낀 점은 채점을 할 때 맞게 하고 싶다면 문제에서 변수들을 잘 파악해야한다는 것이다.
우선 문제를 살펴보면
테스트 케이스를 의미하는 변수 T가 존재한다.
또한 배추를 심은 배추밭의 가로길이 M, 세로 길이 N, 배추를 심은 개수 K가 존재한다.
또한 그 후 배추의 위치를 나타내는 변수론느 x, y가 존재한다.
그럼 일단 6개의 변수가 존재하는 것이다. 그 후 반복문 안에서 다음 배열 인덱스를 담아 줄 ny, nx변수와 최종 개수를 ret할 ret 변수까지 9개가 존재한다.
또한 이 문제는 깊이 탐색 문제이므로 배추의 위치를 표현할 map과 그 배열과 같은 크기의 방문 여부 배열이 필요하다.
#include <iostream>
#include <algorithm>
#include <tuple>
using namespace std;
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
int m,n,k;// 배추 밭 넓이와 배추
int ret;
int x, y; // 배추
int ny, nx;//넥스트 배추
int t;
int a[51][51];
bool visited[51][51];
void dfs(int y, int x){
visited[y][x] = 1;
for(int i=0;i<4;i++){
ny = y + dy[i];
nx = x + dx[i];
if(ny<0||ny > 51 || nx < 0 || nx> 51)continue;
if(a[ny][nx] == 1 && visited[ny][nx] == 0){
dfs(ny, nx);
}
}
return;
}
int main() {
cin.tie(NULL);
cin.tie(NULL);
cin >> t;
while(t--){
fill(&a[0][0], &a[0][0] + 51 * 51, 0); // 0으로 초기화
fill(&visited[0][0], &visited[0][0]+ 51 * 51, 0); // 0으로 초기화
ret= 0;
cin >> m >> n >> k;
for(int i = 0; i < k; i++)
{
cin >> x >> y;
a[y][x] = 1;
}
for(int i=0;i < n;i++){
for(int j = 0; j < m; j++){
if(a[i][j] == 1 && visited[i][j] == 0)
{
dfs(i, j);
ret++;
}
}
}
cout << ret << endl;
}
return 0;
}
내가 작성한 정답은 다음과 같다. 우선 dfs라는 함수를 만들어준 후 위치를 받고 그 안에서 4방향을 탐색하면서 visited배열의 값을 바꿔주며 이동하는 방식이다. 그 후 main문안에서는 그저 문제가 요구하는 흐름대로 전체 t번 반복하면 되고 입력 받는대로 입력을 받고 dfs함수를 실행하는 수를 세어 ret++를 해주면 된다.
내가 이 문제에서 배운 새로운 함수는 fill이라는 함수인데 내가 고민하던 여러 데이터가 들어갈 수 있는 자료구조를 특정한 값으로 초기화 해줄 수 있는 함수라고 한다.
사용법은 다음과 같다.
fill( 시작점 iterator, 끝 iterator, 초기화 하고 싶은 값);
나는 2차원 배열을 0이라는 값으로 초기화 시키고 싶었으므로 fill(&a[0][0], &a[0][0]+ 51 * 51, 0)과 같이 작성해주었다.
'c++ > 알고리즘' 카테고리의 다른 글
[C++] odd-Even Transposition Sort (1) | 2022.03.29 |
---|---|
백준-2468 안전영역 (8) | 2022.03.29 |
백준2178번-미로BFS (0) | 2022.03.28 |
shell sort c++ (0) | 2022.03.23 |
백준 9996 (0) | 2022.03.19 |
댓글