[알고리즘 개인 스터디] 1주차: BFS 문제 풀이(10451, 2178) - 윤현승

서론

평상시에 백준을 꾸준히 풀어야겠다고 마음먹고서 3일 정도 하다가 안 하게 된 적이 대부분이었다.

이번에는 다음학기에 알고리즘 과목도 있어서 꾸준하게 하는 것이 목표이다.

공부 방식은 최대한 골드이하의 쉬운 문제들을 직접 풀면서 가볍게 개념들을 복습하면서 공부할 거고,

언어는 c++로 해볼 것이다.

 

 

BFS 알고리즘

1. 개념

BFS는 너비 우선 탐색의 약자로, 트리 또는 그래프 구조에서 하나의 정점에서 시작해서 인접한 노드들부터 탐색하면서 멀리 떨어진 정점까지 순차적으로 순회하는 방법이다.

간단히 말해서, BFS는 시작점에서부터 가까운 곳부터 차례로 탐색하면서 넓게 퍼져나가는 방법이다.

BFS는 큐(queue)라는 자료구조를 사용하는데, 이유는 큐가 먼저 들어온 것을 먼저 처리하는 특성을 가지고 있어서, 탐색 순서를 보장할 수 있기 때문이다

 

 

2. 문제 1

문제 설명

 

굉장히 간단한 BFS 문제였다 1번째 배열의 값 3 은 1번 노드가 3번 노드를 가리킨다고 이해하면 쉽다.

그림과 같은 사이클이 몇 개 있는지 찾아 개수를 출력하면 된다.

 

풀이

queue를 사용해서 너무 쉬운 그래프 간선대로 bfs를 하면 되는 것이라 설명이 크게 필요 없을 것 같다.

bfs를 돌릴 때 현재 좌표와 다음 좌표를 같이 쓸 때 헷갈리지 않게 변수명을 정하는 것에만 주의를 가지고,

한번 체크했다면 visited배열에 표시해서 중복적으로 계산하지 않도록 해주면 될 것 같다.

 

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

int main(){
    int t, n, curr, next;
    cin >> t;

    while(t--){
        cin >> n;
        int arr[n+1];
        vector<int> visited(n+1, 0);

        // 입력 받기
        for(int i=1; i<n+1; i++){
            cin >> arr[i];
        }

        int answer = 0;
        for(int i=1; i<n+1; i++){
            if(!visited[i]){

                // bfs 돌리기
                queue<int> q;
                q.push(i);
                visited[i] = 1;

                while(!q.empty()){
                    curr = q.front();
                    q.pop();

                    next = arr[curr];
                    if(!visited[next]){
                        q.push(next);
                        visited[next] = 1;
                    }
                }
                answer++;
            }
        }

        cout << answer << endl;
        
    }
}

 

 

 

3. 문제 2

문제 설명

미로를 탈출하는 최단거리를 물어보는 문제이다. 최단거리를 구하는 것은 BFS의 장점 중 하나이다.

문제는 배열에서 1의 값이 있는 길만 이동할 수 있고, 0은 이동할 수 없다고 설명하고 있다.

왼쪽 제일 끝 (1,1)에서 오른쪽 제일 끝 (n, m)까지 이동하는 것이 고정이다.

 

풀이

 

먼저 BFS의 특징상 한 점에서 멀리 있는 점까지 근처점을 통해서 탐색한다고 맨 앞에서 설명했다.

나는 한 점에서 상하좌우로 탐색해서 이동하는 식으로 BFS(너비 우선 탐색) 하기 위해서 dir 2차원 배열을 하나 만들어 주었다.

int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

이런 식으로 만들어주면 밑에서 BFS에서 탐색할 때 코드의 재사용성이 높아질 것을 기대할 수 있다.

 

 

 

그리고 배열에서 탐색을 하는 문제를 풀 때 조심해야 하는 것이 있는데, 바로 배열에 없는 좌표를 탐색하는 것이다.

이런 일을 방지하기 위해 탐색하려는 좌표가 배열 안에 존재하는지 확인하는 is_in함수를 만들어주었다.

bool is_in(int x, int y){
    if(x >= 0 && y >= 0 && x < n && y < m){
        return true;
    }
    return false;
}

 

 

 

BFS 하는 것도 함수로 따로 만들어 주었다.

주의할 점

• 문제 1번과 같이 visited배열을 통해서 이미 탐색한 정점을 체크하기
• is_in함수로 배열 범위를 꼭 체크하기
• 문제에서 주어진 조건인 배열에서 1의 값으로 이루어진 좌표로만 이동하도록 체크하기

최단거리가 몇인지 기록하기 위해서 visited배열에 이동하기 이전 좌표 값에서 +1씩 늘려가면서 기록해 주었다.

void bfs(){
    pair<int,int> p = make_pair(0,0); // 시작 좌표
    queue<pair<int,int>> q;
    q.push(p);
    visited[0][0] = 1;

    while(!q.empty()){
        p = q.front(); q.pop();
        int cur_x = p.first;
        int cur_y = p.second;

        for(int i=0; i<4; i++){
            int next_x = cur_x + dir[i][0];
            int next_y = cur_y + dir[i][1];
            if(map[next_x][next_y] && is_in(next_x, next_y)
            && !visited[next_x][next_y]){
                visited[next_x][next_y] = visited[cur_x][cur_y] + 1;
                q.push(make_pair(next_x, next_y));
            }
        }
    }

 

 

전체코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
#define MAX 101

int map[MAX][MAX];
int visited[MAX][MAX];
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int n, m;
string input;

bool is_in(int x, int y){
    if(x >= 0 && y >= 0 && x < n && y < m){
        return true;
    }
    return false;
}

void bfs(){
    pair<int,int> p = make_pair(0,0); // 시작 좌표
    queue<pair<int,int>> q;
    q.push(p);
    visited[0][0] = 1;

    while(!q.empty()){
        p = q.front(); q.pop();
        int cur_x = p.first;
        int cur_y = p.second;

        for(int i=0; i<4; i++){
            int next_x = cur_x + dir[i][0];
            int next_y = cur_y + dir[i][1];
            if(map[next_x][next_y] && is_in(next_x, next_y)
            && !visited[next_x][next_y]){
                visited[next_x][next_y] = visited[cur_x][cur_y] + 1;
                q.push(make_pair(next_x, next_y));
            }
        }
    }
    

}

int main(){
    cin >> n >> m;

    for(int i=0; i<n; i++){
        cin >> input;
        for(int j=0; j<m; j++){
            map[i][j] = input[j] - '0';
        }
    }

    bfs();

    cout << visited[n-1][m-1] << endl;

    return 0;
}

 

마무리

오랜만에 문제풀이를 하게 되어 많이 어색하였다. 원래 다 알고 있다고 생각한 define을 사용하는 법부터 pair 타입의 변수 선언 방식등 여러 가지 부분에서 구글링을 하면서 풀었다.

 

현재 DP, 재귀, Dijkstra, 여러 가지 정렬과 같은 알고리즘들을 주차별로 진행할 계획인데 다음 주에는 DP를 한번 풀어봐야겠다!