3. BFS Reference Code - 지도 유형,백준 2178,2667,2468,1697,5014

Reference Code

백준 2178 - 미로 탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX_SIZE 101

using namespace std;

// 위, 오른, 아래, 왼
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int n, m; // 행과 열의 수
int dis[MAX_SIZE][MAX_SIZE];

int map[MAX_SIZE][MAX_SIZE]; // 지도
bool visited[MAX_SIZE][MAX_SIZE]; // 방문했는지를 표시하는 지도


// BFS
void bfs(int x, int y){
  
    queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
    q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.

    // 처음 x,y를 방문 했기때문에
    visited[x][y] = true;

    while(!q.empty()){

        // 큐의 현재 원소를 꺼내기
        x = q.front().first;
        y = q.front().second;
        q.pop();

        // 해당 위치의 주변을 확인
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 지도를 벗어나지 않고
            if(0 <= nx && nx < n && 0 <= ny && ny < m){
                // 집이면서 방문하지 않았다면 -> 방문
                if(map[nx][ny] == 1 && visited[nx][ny] == false){
                    visited[nx][ny]=true;

                    // 해당 단지의 집의 수를 증가시킴
                    dis[nx][ny] = dis[x][y] + 1;

                    // 큐에 현재 nx,ny를 추가
                    q.push(make_pair(nx,ny));
                }
            }
        }
    }
}

int main (){

    scanf("%d%d", &n, &m);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)
            //입력을 1개씩 숫자로 끊어서 받습니다 -> %1d
            scanf("%1d", &map[i][j]);
    }
    
    dis[0][0] = 1;
    bfs(0, 0);

    printf("%d\n",dis[n-1][m-1]);
}

 

map, visited 2차원

queue 1차원 pair 로 구현

 

 

 

 

 

 

 

 

 

응용문제)

백준 2667 - 단지 번호 붙이기

www.acmicpc.net/problem/2667

 

#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX_SIZE 25

using namespace std;

// 위, 오른, 아래, 왼
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int n; // 행과 열의 수
int group_id; // 단지의 번호로 첫번째 단지부터 1로 시작
int groups[MAX_SIZE * MAX_SIZE]; // 각 단지별 집의 수

int map[MAX_SIZE][MAX_SIZE]; // 지도
bool visited[MAX_SIZE][MAX_SIZE]; // 방문했는지를 표시하는 지도


// BFS
void bfs(int x, int y){

    queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
    q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.

    // 처음 x,y를 방문 했기때문에
    visited[x][y] = true;
    groups[group_id]++;  

    while(!q.empty()){

        // 큐의 현재 원소를 꺼내기
        x = q.front().first;
        y = q.front().second;
        q.pop();

        // 해당 위치의 주변을 확인
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 지도를 벗어나지 않고
            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                // 집이면서 방문하지 않았다면 -> 방문
                if(map[nx][ny] == 1 && visited[nx][ny] == false){
                    visited[nx][ny]=true;

                    // 해당 단지의 집의 수를 증가시킴
                    groups[group_id]++;

                    // 큐에 현재 nx,ny를 추가
                    q.push(make_pair(nx,ny));   
                }
            }
        }
    }
}



int main (){

    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
            //입력을 1개씩 숫자로 끊어서 받습니다 -> %1d
            scanf("%1d", &map[i][j]);
    }

    // 전체 지도 탐색
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // 집이면서 방문하지 않았다면 -> 방문
            if(map[i][j]==1 && visited[i][j]==false){

                // 해당 지역에 단지 id를 부여하고
                group_id++;

                // 탐색
                bfs(i, j);
            }
        }
    }

    // 단지마다 집들의 수로 오름차순 정렬
    // ID는 1부터 시작
    // 함수 사용법: https://twpower.github.io/71-use-sort-and-stable_sort-in-cpp
    sort(groups + 1, groups + group_id + 1);

    printf("%d\n", group_id);
    for (int i = 1; i <= group_id; i++) {
        printf("%d\n", groups[i]);
    }
}

 

 

 

 

 

 

응용문제) 백준 2468 안전영역

www.acmicpc.net/problem/2468

2468번: 안전 영역

 

#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstring>  // memset

#define MAX_SIZE 101

using namespace std;

// 위, 오른, 아래, 왼
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int n; // 행과 열의 수

int map[MAX_SIZE][MAX_SIZE]; // 지도
bool visited[MAX_SIZE][MAX_SIZE];

// BFS
void bfs(int x, int y, int depth){
  
    queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
    q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.

    // 처음 x,y를 방문 했기때문에
    visited[x][y] = true;

    while(!q.empty()){

        // 큐의 현재 원소를 꺼내기
        x = q.front().first;
        y = q.front().second;
        q.pop();

        // 해당 위치의 주변을 확인
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 지도를 벗어나지 않고
            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                // 집이면서 방문하지 않았다면 -> 방문
                if(map[nx][ny] > depth && visited[nx][ny] == false){
                    visited[nx][ny]=true;

                    // 큐에 현재 nx,ny를 추가
                    q.push(make_pair(nx,ny));
                }
            }
        }
    }
}

int main (){
    int max = -1;
    int cnt[MAX_SIZE] = {0};

    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &map[i][j]);
            if(map[i][j] > max)
                max = map[i][j];
        }
    }
    
    for(int d=0; d<=max; d++){
        // visited 초기화
        memset(visited, false, sizeof(visited));
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] > d && visited[i][j] == false){
                    cnt[d]++;
                    bfs(i, j, d);
                }
            }
        }
    }
    
    int cnt_max = -1;
    int cnt_max_id = -1;
    for(int i=0; i<=max; i++){
        if(cnt[i] > cnt_max){
            cnt_max_id = i;
            cnt_max = cnt[i];
        }
    }
    
    printf("%d\n",cnt[cnt_max_id]);
}
 

 

 

 

- 제일 빠른 경로를 찾는 것이 아니므로 dis 배열을 사용하지 않았다.

- map == 1 인 기준이 아니라, map > depth 기준으로 변경하였다.

- bfs를 여러 번 시행하여 가장 안전 영역이 큰 경우의 수를 찾았다.

- 전형적인 지도 유형의 문제

 

 

 

 

 

 

응용문제) 백준 1697 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX_SIZE 100001

using namespace std;

int n, m; // 수빈, 동생 위치

int dis[MAX_SIZE];
bool visited[MAX_SIZE]; // 방문했는지를 표시하는 배열

// BFS
void bfs(int x){
  
    queue <int> q; // 이용할 큐
    q.push(x);
    int nx;

    // 처음 x를 방문 했기때문에
    visited[x] = true;

    while(!q.empty()){

        // 큐의 현재 원소를 꺼내기
        x = q.front();
        q.pop();

        // 해당 위치의 주변을 확인
        nx = x * 2;
        
        // 지도를 벗어나지 않고, 방문한 적 없으면
        if(nx <= MAX_SIZE-1 && visited[nx] == false){
            visited[nx]=true;

            // 해당 단지의 집의 수를 증가시킴
            dis[nx] = dis[x] + 1;
            
            if(nx == m){
                printf("%d\n", dis[nx]);
                return;
            }

            // 큐에 현재 nx를 추가
            q.push(nx);
        }
        
        // 해당 위치의 주변을 확인
        nx = x + 1;
        
        // 지도를 벗어나지 않고, 방문한 적 없으면
        if(nx <= MAX_SIZE-1 && visited[nx] == false){
            visited[nx]=true;

            // 해당 단지의 집의 수를 증가시킴
            dis[nx] = dis[x] + 1;
            
            if(nx == m){
                printf("%d\n", dis[nx]);
                return;
            }

            // 큐에 현재 nx를 추가
            q.push(nx);
        }
        
        // 해당 위치의 주변을 확인
        nx = x - 1;
        
        // 지도를 벗어나지 않고, 방문한 적 없으면
        if(0 <= nx && visited[nx] == false){
            visited[nx]=true;

            // 해당 단지의 집의 수를 증가시킴
            dis[nx] = dis[x] + 1;
            
            if(nx == m){
                printf("%d\n", dis[nx]);
                return;
            }

            // 큐에 현재 nx를 추가
            q.push(nx);
        
        }
    }
}

int main (){
    
    scanf("%d%d", &n, &m);
    
    if(n == m){
        printf("0\n");
    } else {
        dis[n] = 0;
        bfs(n);
    }
    
}

 

 

- 지도 유형은 아니지만, 지도 레퍼런스를 가지고 풀었다.

- 2차원 배열을 모두 1차원으로 변경

- 세세한 예외 조건들을 설정하는게 까다로운 문제

 

 

 

 

 

 

 

 

응용문제) 백준 5014 스타트링크

 

#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX_SIZE 10000001

using namespace std;

int f, s, g, u, d;

int dis[MAX_SIZE];
bool visited[MAX_SIZE]; // 방문했는지를 표시하는 배열

// BFS
void bfs(int x, int up, int down){
  
    queue <int> q; // 이용할 큐
    q.push(x);
    int nx;

    // 처음 x를 방문 했기때문에
    visited[x] = true;

    while(!q.empty()){

        // 큐의 현재 원소를 꺼내기
        x = q.front();
        q.pop();

        // 해당 위치의 주변을 확인
        nx = x + up;
        
        // 지도를 벗어나지 않고, 방문한 적 없으면
        if(nx >= 1 && nx <= f && visited[nx] == false){
            
            visited[nx]=true;

            // 해당 단지의 집의 수를 증가시킴
            dis[nx] = dis[x] + 1;
            
            if(nx == g){
                printf("%d\n", dis[nx]);
                return;
            }

            // 큐에 현재 nx를 추가
            q.push(nx);
        }
        
        // 해당 위치의 주변을 확인
        nx = x - down;
        
        // 지도를 벗어나지 않고, 방문한 적 없으면
        if(nx >= 1 && nx <= f && visited[nx] == false){
            
            visited[nx]=true;

            // 해당 단지의 집의 수를 증가시킴
            dis[nx] = dis[x] + 1;
            
            if(nx == g){
                printf("%d\n", dis[nx]);
                return;
            }

            // 큐에 현재 nx를 추가
            q.push(nx);
        }
    }
    printf("use the stairs\n");
}

int main (){
    
    scanf("%d%d%d%d%d", &f, &s, &g, &u, &d);
    
    if(s == g){
        printf("0\n");
    } else {
        bfs(s, u, d);
    }
    
}

 

 

 

- 숨바꼭질 문제를 변형해서 작성하였다.

- 역시나 예외 처리에서 꼼꼼하게 따져줘야 했다.