#1012 유기농 배추

문제는 위와 같다. (실버2) 쉬운 dfs/bfs문제였다. 연결요소 문제랑 매우 흡사한 문제이다. 개인적으로 dfs보다 bfs가 더좋은것 같은데 사람들은 dfs를 더많이 쓰는듯;

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

queue<pair<int,int>> q;
int M,N,K; //가로 세로 길이, 배추 개수
int check[51][51];  //방문했는지 확인하는
int a[51][51]; //인접행렬
int dx[] = {0,-1,0,1};  //한칸씩 움직일때 필요
int dy[] = {1,0,-1,0};

void bfs(int x,int y){
  q.push(make_pair(x,y)); check[x][y] = 1;
  while(!q.empty()){
    x=q.front().first; y=q.front().second;
    q.pop();
    for(int k=0;k<4;k++){
      int nx=x+dx[k]; int ny=y+dy[k];
      if(0<=nx&&nx<M && 0<=ny&&ny<N){
        if(a[nx][ny]==0||check[nx][ny]==1)
          continue;         
        q.push(make_pair(nx,ny));
        check[nx][ny]=1;   
      }
    }
  }
}

int main()
{
  freopen("input.txt", "r", stdin);
  int t;
  int cnt;
  cin>>t;
  while(t--){
    cnt=0;
    cin>>M>>N>>K;
    memset(a, 0, sizeof(a));
    memset(check, 0, sizeof(check));
    for(int i=0;i<K;i++){
      int from,to;
      cin>>from>>to;
      a[from][to]=1;
    }
    for(int i=0;i<M;i++){
      for(int j=0;j<N;j++){
        if(a[i][j]==1&&check[i][j]==0){
          bfs(i,j);
          cnt++;
        }
      }
    }
    cout<<cnt<<'\n';
  }
}

코드는 위와 같다.

복습이라도 하라는 듯이 pair클래스를 사용하게 되었다. pair을 통해 x행 y열을 입력 받았고, 이를 2차원 배열 a에 넣었다.

배추는 한곳에만 있기때문에 x행 y열에 1을 대입해야했는데, 나도모르게 x행 y열과 y행 x열에 둘다 1을 넣어버려서 답이 이상하게 나왔다. (이걸로 한시간정도 헤멤;)

 

★배운것

- memset()

: 상당히 편함... 이걸 왜 안찾아봤을까 후회된달까? 여태까지 reset()함수를 직접 만들어서 썼었는데 memset을 쓰도록 해야겠다.

 

- 정점간의 간선을 표현하는것 vs 한 점에 입력하는것

  여태껏 간선을 표현하는 문제를 풀어서 무의식적으로 a[from][to] = 1;  a[to][from] = 1; 을 했었다. 이 문제는 간선을      표현 하는게 아니라 배추의 위치만 표현하는 것이기 때문에 정확히 한곳에만 입력해야했다.

 

++나중에 dfs로도 풀어봐야지