[Algorithm] 2주차 스터디 - 스택, 큐, 덱 / BFS, DFS

 

---

목차

1. 개념 정리

(1) 스택

(2) 큐

(3) 덱

(4) BFS

(5) DFS

 

2. 2주차 필수 문제 풀이

(1) A - 괄호 (백준 9012번)

(2) B - 카드2 (백준 2164번)

(3) C - 알파벳 블록 (백준 27497번)

(4) D - 바닥 장식 (백준 1388번)

(5) E - W키가 빠진 성원이 (백준 28471번)

---

1. 개념 정리

(1) 스택

한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다. (FIrst In Last Out) 따라서 특정 위치에서만 원소가 변경될 수 있는 특성상  원소의 추가와 제거의 시간 복잡도가 모두 O(1)이다. 또한  스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않는다.

(2) 큐

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. (First In First Out) 큐에서 연산의 시간복잡도는 스택처럼 원소의 추가와 제거 모두 O(1)이다. 하지만  스택과는 다르게 큐는 배열로 구현하면 삭제가 발생할 때 마다 앞쪽에 쓸모없는 공간이 계속 생긴다.

(3) 덱

양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조로, 스택과 큐를 덱의 특수한 예시라고 생각할 수 있다. 덱에서도 삽입, 삭제, 제일 앞/뒤 원소의 확인 시간 복잡도가 다 O(1)이다. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하지만 예외적으로 STL deque에서는 인덱스로 원소에 접근할 수 있다.

(4) BFS

BFS(Breadth First Search)는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 큐를 사용하여 순회를 처리하는 알고리즘으로 이해할 수 있다. 시간복잡도는 행이 R, 열이 C개일 때 O(RC)이다. 

(5) DFS

DFS(Depth First Search)는 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘이다. 스택을 써서 다차원 배열의 순회를 처리하는 알고리즘으로 이해할 수 있다. DFS는 BFS와 달리 거리 측정을 할 수 없기 때문에 다차원 배열에서 순회하는 문제를 풀 때는 쓸 수 없고, 그래프와 트리에서 사용할 수 있다.

---

 

2. 2주차 필수 문제 풀이

해당 주차는 C++ 을 사용했습니다

(1) A - 괄호 (백준 9012번)

9012번: 괄호 (acmicpc.net)

9012번: 괄호

 

이 문제는 주어진 문자열의 괄호 구조가 올바르게 구성되어 있는지를 판별하고자 한다. 이때 올바른 괄호 구조란,
모든 열린 괄호에 대해 짝을 이루는 닫힌 괄호가 존재하며, 괄호의 순서가 올바르게 배치된 것이다.

 

📢 Stack 사용

✔️ 문자열을 하나씩 검토하면서 열린 괄호를 만나면 Stack에 추가하고, 닫힌 괄호를 만나면 Stack 값을 지운다.

✔️ 만약 닫힌 괄호를 만났을 때 Stack이 비어 있다면, 짝이 맞지 않는 괄호가 존재하는 것이므로 false를 반환하고 모든 문자열 검사 후 Stack이 비어있으면 true를 반환한다.

 

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool check(string str){
    int len = (int)str.length();
    stack<char> st;

    for(int i=0; i<len; i++){
        char c = str[i];

        if(c == '('){
                st.push(str[i]);
            }else{
                if(!st.empty()){
                    st.pop();
                }else{
                    return false;
                }
            }

        }
    return st.empty();
}

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

    for(int i=0; i<n; i++){
        string str;
        cin >> str;

        if(check(str)){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
            }
        }
    return 0;
}

 

(2) B - 카드2 (백준 2164번)

2164번: 카드2 (acmicpc.net)

2164번: 카드2

 

이 문제는 숫자 n을 받아 1부터 n까지의 숫자가 쓰여 있는 카드를 작은 숫자가 위로 가게 쌓는다. 그 뒤 맨 뒤의 카드를 제거하고 뒤에서 두 번째 카드는 카드들의 맨 앞으로 이동시킨다. 이 과정을 n-1번 반복한 후 남아있는 마지막 카드의 숫자를 출력한다.

 

📢 Deque 사용

✔️ 주어진 숫자를 n을 받아 1부터 deque에 역순으로 저장한다.

✔️  맨 뒤 요소를 삭제하고, 새롭게 맨 뒤가 된 요소를 추출한 뒤 해당 요소 또한 삭제한다. 추출된 요소는 deque의 맨 앞에 추가한다. 이 과정은 카드가 한 장만 남을 때까지 반복된다.

 

#include <iostream>
#include <deque>

using namespace std;
int check();

int main(){
    int n ;
    n = check();
    return 0;
}


int check(){
    int n;
    cin >> n;
    std::deque<int> deq;

    for(int i=1; i <= n; i++){
        deq.push_front(i);
    }
    int len = deq.size();
    for(int i=0; i<len-1; i++){
        deq.pop_back();
        int output = deq.back();
        deq.pop_back();
        deq.push_front(output);
    }
    cout << deq.back() << endl;
    return deq.back();
}

 

(3) C - 알파벳 블록 (백준 27497번)

27497번: 알파벳 블록 (acmicpc.net)

27497번: 알파벳 블록

 

이 문제에서는 '1', '2', '3'의 세 가지 명령어를 받는다. '1' 명령을 받으면 문자열 맨 뒤 주어진 문자열을 추가, '2'는 문자열의 앞부분에 문자 추가, '3'은 가장 최근에 추가된 문자를 문자열에서 제거한다. 최종적으로 남은 문자열을 출력하되, 빈 문자열일 경우0을 출력한다.

 

📢 Deque와 Stack 사용

✔️ '1', '2' 명령어를 받았을 경우 각각 deque의 앞, 뒤에 주어진 문자열을 추가하고 stack에는 들어온 순서대로 명령어 번호를 저장한다.

✔️ '3' 명령어를 받았을 경우 stack의 가장 상단 요소를 확인하여 deque의 앞 또는 뒤에서 적절한 문자열을 제거한다.

 

#include <iostream>
#include <deque>
#include <stack>
#include <sstream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    deque<string> deq;
    stack<string> keys;

    for(int i=0; i<n; i++){
        //cout << i + 1 << "번째 줄"<<endl;
        string first, second;
        cin >> first;

        if(first == "1"){
                cin >> second;
                deq.push_back(second);
                keys.push(first);

            //for (int o=0; o<deq.size(); o++){
            //    cout << deq[o];
            //}
            //cout << endl;

        }
        if(first == "2"){
                cin >> second;
                deq.push_front(second);
                keys.push(first);
            //for (int o=0; o<deq.size(); o++){
            //    cout << deq[o];
            //}
            //cout << endl;
        }
        if(first == "3" && deq.empty() != true && keys.empty() != true){
            //3
            if(keys.top() == "1"){
                deq.pop_back();
            } else if(keys.top() == "2"){
                deq.pop_front();
            }
            //if (!keys.empty()){
                keys.pop();    
            //}

        }
    }
    if(deq.empty()){
        cout << 0;
    }else {
        for (int i=0; i<deq.size(); i++){
            cout << deq[i];
        }
    }
    return 0;
}

 

(4) D - 바닥 장식 (백준 1388번)

1388번: 바닥 장식 (acmicpc.net)

1388번: 바닥 장식

 

이 문제에서는 주어진 타일 배열에서 '-'(가로바)와 '|'(세로바)를 구분하여 총 개수를 세고자 한다. 이때 연속된 '-'(가로바) 또는 '|'(세로바)는 1개로 간주된다.

 

📢 Vector와 Stack 사용

✔️ 가로줄과 세로줄을 따로 분리하여 가로줄에서는 가로바, 세로줄에서는 세로바를 센다.

✔️ bool 함수를 이용하여 처음 바를 만날 때마다 바의 개수를 하나씩 증가시키고, 바가 연속적으로 나타나면 카운드하지 않는다.

 

#include <iostream>
#include <stack>
#include <vector>
#include <sstream>


using namespace std;

int rowCheck();
int columnCheck();


int main()
{
    int rows;
    int columns;
    cin >> rows >> columns;
    vector<string> tiles(rows);
    //메인에서 타일 배치를 받기
    //각 Row를 Stack<Char>로
    // rows개 만큼의 stack을 저장할 곳이 필요
    for(int i = 0; i<rows; i++){
        cin >> tiles[i];
    }

    int cnt = 0;
    for (int j = 0; j < rows ; j++){
        bool bar = false;

        for(int i = 0; i < columns ; i++){
            if (tiles[j][i] == '-'){
                if (bar == false){
                    cnt++;
                }
                bar = true;
            }else {
                bar = false;
            }


        }
    }
    //cout << "가로바 개수 : " << cnt << "개"<<endl;

    for (int j = 0; j < columns ; j++){
        bool bar = false;

        for(int i = 0; i < rows ; i++){
            if (tiles[i][j] == '|'){
                if (bar == false){
                    cnt++;
                }
                bar = true;
            }else {
                bar = false;
            }


        }
    }
    //cout << "최종 개수 : " << cnt << "개"<<endl;
    cout << cnt;
    return 0;
}

 

(5) E - W키가 빠진 성원이

28471번: W키가 빠진 성원이 (acmicpc.net)

28471번: W키가 빠진 성원이

 

이 문제는 주어진 NxN 게임판 위 시작 지점 '.'에서 출발하여 'F'으로 표시된 곳으로 이동하고자 한다. 이때 8방향 중 위쪽으로는 이동하지 못하며 '#'으로 표시되는 벽, 또는 보드의 경계를 벗어나는 칸으로는 이동할 수 없다.

 

📢 DFS 활용

✔️ F점에서 시작하여 아래 방향키를 이용하지 않고 '.'까지 갈 수 있는 방법의 수를 구한다.

✔️ 시작 지점 'F'에서 출발하여 가능한 모든 방향을 탐색했을 때 그 좌표가 '.'  좌표에 해당하면 그 점으로 이동한다. 모든 이동 경로에 대해 가능한 경우를 계속해서 탐색하고,  탐색이 불가능한 칸이거나 보드의 경계를 벗어나는 경우에는 탐색을 중지한다.

 

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

int dx[] = {-1, -1, -1, 1, 0, 1, 0}; // 7방향 이동에 대한 x축 변화 (W 제외)
int dy[] = { 0,  1, -1, 1, -1,-1, 1}; // 7방향 이동에 대한 y축 변화 (W 제외)

void printboard(vector<vector<char>>& board){
    cout<<"=============="<<endl;
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board.size(); j++) {
            cout << board[i][j];
        }
        cout<<endl;
    }
    cout<<"=============="<<endl;
}

void dfs(vector<vector<char>>& board, int x, int y) {
    board[x][y] = 'V'; // 방문 표시
    //printboard(board);
    for (int k = 0; k < 7; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board.size() && board[nx][ny] == '.') {
            //cout << "going to : (" << nx << "," <<ny<<")"<<endl;
            dfs(board, nx, ny);
        }
    }

}

int main() {
    int N;
    cin >> N;

    vector<vector<char>> board(N, vector<char>(N));
    pair<int, int> start; // 시작 지점 위치

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'F') {
                start = {i, j}; // 시작 지점 위치 저장
            }
        }
    }
    dfs(board, start.first, start.second);

    int count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 'V') {
                count++;
            }
        }
    }
    //F 까지 V 표시가 되었으므로 - 1
    cout << count - 1 << endl;
    return 0;
}

 

출처: [실전 알고리즘] 0x05~0x09강 BaaaaaaaarkingDog