[BOJ / C++] #1012 유기농 배추
🥬 문제풀이
map에서 서로 인접한 배추 그룹의 개수를 세주는 문제이다.
BFS로 구현하였고, 이미 방문한 것은 따로 visited배열 없이 map[i][j]=2로 만들어 진행했다.
- 입력 받기
- 맵을 완전탐색하면서 map[i][j]==1 (배추가 있는 곳)이 나오면 bfs(i,j)실행해주기.
- bfs
- i,j좌표를 큐에 삽입, map[i][j]=2로 만들어줌으로써 방문했음으르 표시
- while(!q.empty())로 인접한 것들을 모두 삽입해주며 bfs실행
- bfs 함수를 빠져나오고 나면, 하나의 배추 그룹을 센 것이므로 cnt++
🥬 코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 51
int map[MAX][MAX];
int M, N, K;
//상우하좌
int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};
void bfs(int i, int j){
queue<pair<int,int>> qq;
qq.push(make_pair(i,j));
map[i][j]=2; //이미 방문한 곳은 2로 만들어주기.
while(!qq.empty()){
int r=qq.front().first;
int c=qq.front().second;
qq.pop();
for(int k=0;k<4;k++){
int nr=r+dr[k];
int nc=c+dc[k];
if(nr<0||nr>N-1||nc<0||nc>M-1||map[nr][nc]!=1) continue;
qq.push(make_pair(nr,nc));
map[nr][nc]=2;
}
}
}
int main(){
int T;
cin>>T;
for(int t=0;t<T;t++){
memset(map,0,sizeof(map));
int cnt=0;
cin>>M>>N>>K;
for(int i=0;i<K;i++){
int c, r;
cin>>c>>r;
map[r][c]=1;
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(map[i][j]==1) {
bfs(i,j);
cnt++;
}
}
}
cout<<cnt<<"\n";
}
}
45' : bfs에서 계속 메모리 오류가 났다. pop하고 나서야 방문했다고 표시했기 때문 push할 때 표시해주기.
Author And Source
이 문제에 관하여([BOJ / C++] #1012 유기농 배추), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inryu/BOJ-C-1012-유기농-배추저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)