탐색

2178번: 미로 탐색

보통은 2차원의 맵을 돌면서 일정 조건 만족하는 최소 경로 찾기로 많이 나옴!

종류에는 크게 BFS, DFS가 있음!

1. DFS (상하좌우)

   재귀로 탐색 구현하는 방법

   • 장 : 빠른 구현이 가능 ( 재귀 함수만 만들면 된다)
   • 단 : 무조건 탐색해야하는 맵을 전부 돌아야 끝이 난다 ( 오래 걸림)

2. BFS

   • 장 : 찾아야 하는 칸에 도달하게 되면 프로그램 종료 가능
   • 단 : queue를 이용한 구현으로 다소 귀찮음

삼성 코딩테스트에서 꼭 나오는 유형,, 많이 나온다

2667번: 단지번호붙이기

중요하게 고려해야할 점

1. visit 필수 (dfs든 bfs든 체크해야함)
2. 어떤 탐색 알고리즘을 사용할 것인가 (BFS를 쓰면 확률이 높다)

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
#define MAX 26

int n,cnt=0;
string arr[MAX];
bool visited[MAX][MAX]={0,};
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<int> result;
queue<pair<int,int>> q;

void bfs(int x,int y) { //한 단지 뭉치를 세는 함수 
    q.push({x,y});
    visited[x][y]=true;
    cnt++;

    while(!q.empty()) {
        int a = q.front().first; // queue에서 꺼낸 좌표 
        int b = q.front().second;
        q.pop();
        for(int i=0;i<4;i++) { //상하좌우 찾기 
            int nx = a + dx[i]; //새로운 상하좌우 반영한 좌표 nx, ny 
            int ny = b + dy[i];
            if(0<=nx && 0<=ny && nx <n && ny < n && visited[nx][ny]==false && arr[nx][ny]=='1') {
                q.push({nx,ny});
                visited[nx][ny]=true;
                cnt++;
            }
        }
    }
}

int main() {
	
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);
    
    for (int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(arr[i][j]=='1' && visited[i][j]==false) {
                cnt =0; //단지 수 
                bfs(i,j);
                result.push_back(cnt);
            }
        }
    }

    sort(result.begin(),result.end());
    
    cout << result.size() << "\\n";
    printf("%d\\n",result.size());
    for (int i=0;i<result.size();i++) {
        printf("%d\\n",result[i]);
    }
}