3. Stack & Queue (2) - 활용

스택과 큐를 활용한 응용 예제 다뤄보기

---

1. Mazing Problem (미로 탐색) — Stack으로 DFS 구현

• 미로 탐색은 그래프 탐색 문제로 볼 수 있음.
• 목표: 출발지에서 도착지까지 경로가 있는지, 경로를 찾는 것.
• DFS(Depth-First Search)를 스택으로 비재귀 방식으로 구현하면 경로를 따라 깊게 탐색함.
• 스택 사용 이유: 재귀 호출 스택을 대신해 현재 경로를 보관하기 위함.

 

- 상태 표현

• 미로를 2차원 배열 maze[row][col] 로 표현.
• 벽 = 1, 통로 = 0, 방문 표시를 위해 별도 visited 배열 혹은 maze 값을 변경 가능.
• 좌표는 (r, c) 쌍. 스택에는 좌표를 저장.

 

- 알고리즘 (스택 기반 DFS, 경로 복원 포함)

1. 스택에 시작 좌표 push, 방문 표시.
2. 스택이 비어있지 않은 동안:
   • 스택의 top을 확인(또는 pop) → 현재 위치 cur.
   • cur 이 목적지이면 종료. (경로는 스택 내용으로 추적 가능)
   • 현재 위치에서 4방(상,우,하,좌) 중 방문하지 않은 통로가 있으면 그 이웃을 push하고 방문 표시, 다음 반복에서 그 이웃을 탐색(즉, 깊이 우선).
   • 만약 더 이상 갈 곳이 없으면 pop(백트래킹).
3. 목적지에 도달하면 스택에 쌓인 좌표들이 경로(또는 역순 경로)가 된다.

 

- C 코드 (간단한 예시)

#include <stdio.h>
#include <stdlib.h>

typedef struct { int r, c; } Point;

typedef struct {
    Point *data;
    int top, cap;
} Stack;

Stack* createStack(int cap) {
    Stack *s = malloc(sizeof(Stack));
    s->data = malloc(sizeof(Point)*cap);
    s->top = -1; s->cap = cap;
    return s;
}
void push(Stack *s, Point p) {
    if (s->top + 1 == s->cap) {
        s->cap *= 2;
        s->data = realloc(s->data, sizeof(Point)*s->cap);
    }
    s->data[++s->top] = p;
}
Point pop(Stack *s) { return s->data[s->top--]; }
Point peek(Stack *s) { return s->data[s->top]; }
int isEmpty(Stack *s) { return s->top == -1; }

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int dfsMaze(int R, int C, int maze[R][C], Point start, Point goal) {
    int visited[R][C];
    for (int i=0;i<R;i++) for (int j=0;j<C;j++) visited[i][j]=0;

    Stack *st = createStack(100);
    push(st, start);
    visited[start.r][start.c] = 1;

    while (!isEmpty(st)) {
        Point cur = peek(st);
        if (cur.r == goal.r && cur.c == goal.c) {
            // 경로 출력 (스택 내용이 경로)
            printf("경로 발견 (역순):\n");
            for (int i=st->top;i>=0;i--) printf("(%d,%d) ", st->data[i].r, st->data[i].c);
            printf("\n");
            return 1;
        }
        int moved = 0;
        for (int k=0;k<4;k++) {
            int nr = cur.r + dr[k], nc = cur.c + dc[k];
            if (nr>=0 && nr<R && nc>=0 && nc<C && !visited[nr][nc] && maze[nr][nc]==0) {
                visited[nr][nc] = 1;
                push(st, (Point){nr,nc});
                moved = 1;
                break; // 깊이 우선: 한 방향으로 계속
            }
        }
        if (!moved) pop(st); // 막다른 길이면 백트래킹
    }
    printf("경로 없음\n");
    return 0;
}

 

- 시간/공간 복잡도

• 시간: 모든 칸을 최대 한 번 방문 → O(R×C)
• 공간: 방문 배열 O(R×C), 스택 최악 O(R×C)

 

- 팁 및 변형

• BFS(Queue 사용) 로 최단 경로을 찾을 수 있음(가중치 없는 그래프).
• 경로 복원은 부모 배열(parent[r][c]) 을 저장하면 깔끔함.
• 스택 DFS는 깊이 우선이므로 특정 경로(깊은 경로)를 먼저 찾음, 최단 경로 보장 X.

스택 기반 DFS는 구현이 단순하고 경로 추적에 유리. 최단 경로 보장X → 최단이 필요하면 BFS(큐) 사용.

---

2. Expression Evaluation (수식 계산) — 스택 활용

- 목표

• 중위 수식(infix) 을 후위 수식(postfix, Reverse Polish Notation) 으로 변환한 뒤 평가.
• 이유: 후위 표기는 괄호와 우선순위 처리가 쉬워 바로 스택으로 계산 가능.

=> 3 + 4 * 2 (중위표기)를 쓸 경우 컴퓨터는 괄호나 우선순위를 사람처럼 해석하지 못함.

때문에 후위표기 (3 + 4 * 2   →   3 4 2 * +) 방식으로 바꾸어서 계산하는 것이 필요

 

- 다루는 연산자

• 이 예시에서는 + - * / ^ ( ) 를 다룸.
• 우선순위: ^  >  *   /  >  +  -
• ^는 오른쪽 결합성(right-associative) (예: 2^3^2 = 2^(3^2)).

 

- 전체 흐름

  step 1) 중위 → 후위 변환 (Shunting-yard 알고리즘)

 

++++ 후위 변환 방법!

3 + 4 * 2 이걸 변환한다고 했을 때

읽은 토큰	출력(결과)	스택(연산자 보관용)
3	3
+	3	+
4	3 4	+
*	3 4	+ * ← *의 우선순위가 +보다 높아서 그냥 push
2	3 4 2	+ *
(끝)	3 4 2 * +

 : 최종 후위 표기: 3 4 2 * +

 

 

 step 2) 후위 수식 평가 (스택으로 계산)

3 + 4 * 2 를 후위로 바꾼 3 4 2 * + 이걸 stack으로 계산하면

읽은 토큰동작스택 상태

읽은 토큰	동작	스택 상태
3	숫자 → push	[3]
4	숫자 → push	[3, 4]
2	숫자 → push	[3, 4, 2]
*	4 * 2 = 8 → push	[3, 8]
+	3 + 8 = 11 → push	[11]
끝	결과 = 11	✅

 

정리하자면,

1) 중위 → 후위 변환	2) 후위 평가
피연산자(숫자)는 출력 큐에 바로 보냄. 연산자는 스택(top)과 우선순위를 비교: 현재 연산자 op1, 스택 top op2: op2의 우선순위가 op1보다 크거나 같고 op1이 왼쪽 결합이면 op2를 출력(팝). op1이 오른쪽 결합(예: ^)이면 우선순위가 엄격히 큰 경우만 팝. ( 은 스택에 push, ) 를 만나면 ( 가 나올 때까지 팝하여 출력. 모든 토큰 처리 후 스택에 남은 연산자 모두 출력.	토큰을 왼쪽부터 읽는다: 숫자면 스택에 push 연산자면 스택에서 필요한 개수의 피연산자를 pop, 연산 후 결과 push 끝나면 스택의 top이 결과.

 

- 시간/공간 복잡도

• 중위→후위: 입력 길이 n 처리 → O(n)
• 후위 평가: 토큰 수에 대해 O(n)
• 전체: O(n) 시간, 스택 공간 O(n)

중위→후위로 변환 후 후위 평가가 안정적. 스택으로 연산자와 피연산자를 분리해서 처리함.