아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.
Stack
Insert/Delete만 제공
Push/Pop이라고 부름
Last in, First Out
성능 : Push O(1), Pop O(1)
Stack Pointer(SP) : 스택의 최상위 부분. 주로 다음 저장될 위치, 즉 빈 공간을 지칭한다.
Stack의 구현
int Stack[N];
int SP;
int init() {
SP = 0;
}
int isEmpty() {
return SP == 0;
}
int Push(int x) {
Stack[SP] = x;
SP++;
}
int Pop() {
SP--;
return Stack[SP];
}
SP의 범위에 관련된 코드는 적혀있지 않다. (이를 방지하지 않으면 오류가 날 수 있지만, 현 상황에선 제외했다.)
Queue
Insert/Delete만 제공
First in, First Out
성능 : Insert O(1), Pop O(1)
Head & Tail : Queue의 제일 앞 부분을 Head, 제일 뒷 부분을 Tail이라한다.
Head와 Tail을 이용하기 때문에 자료의 끝부분에 공간이 없어도 앞부분에 공간이 있다면 해당 공간을 활용하고 Head와 Tail만 잘 표시해주면 된다. 만약 Head와 Tail이 겹치면 비어있거나, 꽉 찬 것이다.
Queue의 구현
int Queue[N];
int Head, Tail;
int init() {
Head = 0;
Tail = 0;
}
int isEmpty() {
return Head == Tail;
}
int insert() {
Queue[Tail] = x;
Tail++;
Tail = Tail % N; // Tail이 돌아오는 경우
}
int delete() {
int oldHead = Head;
Head++;
Head = Head % N;
return Queue[oldHead];
}
최대한 간단한 핵심기능만 구현한 것이다.
미로찾기 : Stack, Queue 응용
0은 열린 좌표, 1은 닫힌 좌표를 뜻한다.
좌표를 저장할 수 있어야 한다.
경로를 저장해놓고 해당 경로를 활용해 다시 돌아갈 수 있어야 한다.
DFS 명시적 stack
int Map[M][N]; // 미로
int i,j; // 현재 위치
int Find() {
i = j = 0;
while () {
if (i == M - 1 && j == N - 1) // 목적지 도착
// (i, j+1) , (i, j-1), (i+1, j), (i-1, j) 중 0이 있는가?
// 0이 있으면 전진 (아래 코드는 예제)
Push(i);
Push(j); // 스택에 i,j 두 값 push
Map[i][j] = '*';
j++;
// 0이 없으면 후진, 후진 시 stack empty면 실패로 처리.
j = Pop();
i = Pop();
}
}
1. (0,0)에서 특정 위치 (s,t)로 가는 길이 있다 = (0,0) , (a1,b1), (a2,b2), ..., (s,t)인 좌표가 있다.
2. 인접한 쌍에서는 좌표값 둘 중 한 숫자만 1 차이가 난다.
3. Map의 전진 가능한 모든 좌표에 초기에 0(갈수있음)이 적혀 있다.
위와 같은 상황에서 알고리즘은 (s,t)를 반드시 방문한다.
길이 있는데 즉, 0이 존재하는데 그를 두고 가지 않는 것은 모순 => 반드시 성립됨이 증명
한 칸에서 사용하는 시간은 상수시간이다. (스택에 넣고, 전진 혹은 후진 작업 수행)
따라서 한 칸에서 일어나는 일을 모든 칸에 적용하면 시간복잡도는 O(MN), 미로의 크기만큼이 된다.
BFS 명시적 Queue
int Map[M][N];
int i, j;
int Find() {
queueInsert(0, 0);
while() {
(i, j) = QueueDelete(); // Queue가 Empty이면 실패
// Map[i][j] == 0 인 경우만
Map[i][j] = '*'; // 목적지 확인
// (i, j+1) , (i, j-1), (i+1, j), (i-1, j) 중 0인 좌표를 Queue에 Insert
}
}
Stack에서의 시간복잡도 : O(N), 전체 노드가 스택에 들어갔다 나오는 횟수는 N-1번(엣지갯수)
Matrix에서의 시간복잡도 : O(N^2), 한 col에서 1을 전부 가지고 있다면 최대 O(N^2)의 시간 복잡도를 가질 수 있지만 한 col이 그 만큼 1을 많이 가지고 있어 다른 col에서는 시간이 소요되지 않는다. 즉, 어떤 형태를 가지더라도 결국은 전체 1의 갯수 *N 의 시간복잡도를 가진다. 따라서 전체 시간복잡도는 O(N^2)이다.
연결관계를 위와 같이 나타낼 수도 있다.
이처럼 나타낼 경우 Matrix에서의 시간복잡도가 줄어들 수도 있다. 한 row에서 지난번 탐색한 위치를 기억한다면 O(N)만으로 모든 위치 정보를 확인할 수도 있다.
