[자료구조] #8 Queue(2)

• STL Queue

 

STL Queue의 API는 다음과 같다.

#include <queue>

std :: queue<data type> name; // Queue 선언

void name.push(data_type x); // enqueue
data_type name.front(); // peek
void name.pop(); // dequeue
int name.size();
bool name.empty();

 

 

• 미로 탐색 문제

 

문제 정의

Input : 2차원 배열의 미로

Output : 성공 or 실패

즉 s에서 t로 갈 수 있냐는 문제이다.

 

길찾기 방법

DFS(Depth First Search) : 깊이 우선 탐색 - 스택 기반 동작

BFS(Breadth First Search) : 넓이 우선 탐색 - 큐 기반 동작

 

주의할 점

• 갔던 길을 다시 가지 않는다.

 

• [ ←, →, ↓, ↑ ] 순서대로 본다.

 

• DFS

Main idea : 막다른 길(deadend)이 나올 때까지 한 방향으로 계속 이동한다.

스택은 다음 위치로 가야하는 정보를 기록한다.

따라서 deadend에 도착했을 때 Last branch를 파악할 수 있다.

 

점프하는 느낌으로 이해하면 쉽다.

 

• 예시 문제

 

이동할 수 있는 조건은 이전에 가지 않았던 곳 + 통로여야 한다.

 

만약 사람이 아래를 먼저 봤다면 (3,1)과 (2,2) 순서가 달라져 있을 것이다.

 

(4,1)에서 (2,1)로 점프할 수 있는 이유는 전 시점에서 다음으로 갈 곳을 미리 체크해두었기 때문이다.

만약 한 곳이 막혀있어 문제 해결이 불가능하다면 false가 반환된다.

 

• C++ 구현

class Cell {
public:
    int row; // 행 인덱스
    int col; // 열 인덱스
    Cell(int r = 0, int c = 0) { row = r; col = c; }
};

// 미로의 크기를 나타내는 상수
const int MAZE_SIZE = 6;

// 미로의 모습을 나타내는 이차원 배열
char map[MAZE_SIZE][MAZE_SIZE] = {
    {'1', '1', '1', '1', '1', '1'},
    {'s', '0', '1', '0', '0', '0'},
    {'1', '0', '0', '0', '1', '0'},
    {'1', '0', '1', '0', '1', '0'},
    {'1', '0', '1', '0', '1', '0'},
    {'1', '1', '1', '1', '1', 't'},
};

// 방문한 셀을 표시하는 이차원 배열
bool visited[MAZE_SIZE][MAZE_SIZE] = {false, };

// 주변 셀을 탐색하기 위한 방향 벡터
vector<Cell> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 주어진 좌표가 미로 내에 있는지와 방문한 셀인지를 확인하는 함수
bool is_valid(int r, int c) {
    // 미로 밖으로 나가는 경우나 이미 방문한 경우에는 유효하지 않음
    if (r < 0 || c < 0 || r >= MAZE_SIZE || c >= MAZE_SIZE)
        return false;
    // 이미 방문한 경우에도 유효하지 않음
    if (visited[r][c] == true)
        return false;
    // '0' 또는 't'인 경우에만 유효함
    else
        return map[r][c] == '0' || map[r][c] == 't';
}

// DFS를 이용하여 미로를 탐색하는 함수
bool dfs(int s_r, int s_c) {
    // DFS 탐색을 위한 스택 선언
    deque<Cell> s;
    // 시작 위치를 스택에 추가
    Cell start(s_r, s_c);
    s.push_back(start);
    
    // 스택이 비어있을 때까지 반복
    while (!s.empty()) {
        // 스택에서 현재 위치를 꺼냄
        Cell here = s.back();
        s.pop_back();
        int r = here.row;
        int c = here.col;
        
        // 도착지점에 도달한 경우 탐색 종료
        if (map[r][c] == 't')
            return true;
        
        // 현재 위치를 방문했는지 확인
        if (visited[r][c] == false) {
            // 현재 위치를 방문했음을 표시
            visited[r][c] = true;
            // 현재 위치의 주변을 탐색하여 스택에 추가
            for (auto direction : directions) {
                int next_r = r + direction.row;
                int next_c = c + direction.col;
                // 유효한 위치라면 스택에 추가
                if (is_valid(next_r, next_c))
                    s.push_back(Cell(next_r, next_c));
            }
        }
    }
    // 탐색을 마쳤지만 도착지점에 도달하지 못한 경우
    return false;
}

 

• BFS

Main idea : 시작 위치에서 갈 수 있는 위치를 모두 체크해두는 방식이다.

 

BFS는 방문 체크를 하고 큐에 넣어두는 방식이라는 점에서 DFS와 다르다.

(DFS는 스택에서 pop하면서 체크)

 

• 시간복잡도 분석

 

DFS와 BFS 모두 상수시간만큼 연산이 반복된다.

따라서 while loop의 반복횟수를 파악하는 것이 핵심이다. 

 

Worst case는 모든 통로를 다 방문하는 경우이다.

결국 스택에 아이템이 몇개 들어갔냐가 반복문의 반복 횟수를 결정한다.

n : # of rows / m : # of columns