음료수 얼려 먹기

전형적인 DFS/BFS문제이다. 그냥 map을 돌면서 연결된 영역의 개수를 구해주면 되는 문제이다. DFS로 풀수도 있고 BFS로도 풀 수 있다. 연습을 위해 두가지 코드 모두 작성하였다.

 

- BFS코드

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

int n,m,cnt;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int map[1001][1001];
int visited[1001][1001];
queue<pair<int,int>> q;

void bfs(int x,int y){
  q.push(make_pair(x,y));
  visited[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<n&&0<=ny&&ny<m){
        if(map[nx][ny]==0&&visited[nx][ny]==0){
          q.push(make_pair(nx,ny));
          visited[nx][ny]=1;
        }
      }
    }
  }
}

int main()
{
  freopen("input.txt","r",stdin);
  cin>>n>>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]==0 && visited[i][j]==0){
        bfs(i,j);
        cnt++;
      }
    }
  }
  cout<<cnt;
}

 

- DFS 코드

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

int n,m,cnt;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int map[1001][1001];
int visited[1001][1001];


void dfs(int x,int y){
  visited[x][y]=1;
  for(int k=0;k<4;k++){
    int nx=x+dx[k];
    int ny=y+dy[k];
    if(0<=nx&&nx<n&&0<=ny&&ny<m){
      if(map[nx][ny]==0&&visited[nx][ny]==0){
        dfs(nx,ny);
      }
    }
  }
}

int main()
{
  freopen("input.txt","r",stdin);
  cin>>n>>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]==0 && visited[i][j]==0){
        dfs(i,j);
        cnt++;
      }
    }
  }
  cout<<cnt;
}

오랜만에 DFS코드를 작성하니깐 조금 어색했다. 아무튼 두 방법 다 어렵지는 않아서 쉽게 쓸 수 있었다.