문제 소개
이번 문제는 미로 찾기이다.
쥐 한 마리가 미로에 갇혀있다. 주어진 미로에서 출구를 찾는 과정을 출력하는 프로그램을 만드는 것이 목표이다.
int maze[][6] = {
{X, X, X, X, X, X},
{S, O, O, O, O, X},
{X, O, X, O, X, X},
{X, X, X, O, O, E},
{X, X, X, X, X, X} };나중에 다시 나오겠지만 미로는 위와 같이 2차원 배열로 주어진다. O와 X는 지나갈 수 있는지 여부를 가리키며, S는 미로의 입구(Start), E는 미로의 출구(End)를 의미한다. 코드를 볼 때 의미를 직관적으로 알 수 있도록 매크로 상수를 사용했다.
왜 스택인가
주어진 미로를 그림으로 나타낸 것이다. 노란색 칸의 S는 시작점, 초록색 칸의 E는 끝점이다.
쥐는 S에서 시작하여 주변(4방향)에 이동 가능한 칸을 찾는다. 시작할 당시에는 이동할 수 있는 점이 바로 오른쪽 칸 ([1][1]) 뿐이므로 그곳으로 이동한다.
쥐가 다시 주변에 이동 가능한 칸을 탐색한다. 오른쪽([1][2])과 아래[2][1]) 방향의 두 갈래 길이 나왔다. 쥐가 아래로 먼저 간다고 가정하자. 아래 방향이 출구가 아닐 수도 있으므로 오른쪽으로도 갈 수 있었다는 사실을 기억해야 막혔을 때 돌아올 수 있다.
아래([2][1])로 왔으나 온 길을 제외하고는 진행할 수 있는 칸이 존재하지 않는다. 따라서 maze[1][2]로 가야 한다.
만약 아래([2][1])로 계속 갈 수 있었고, 도중에 갈래길 또 만났다고 하자. 그랬다면 쥐가 아까의 오른쪽([1][2])으로 돌아오는 것은 최근에 만난 갈래길을 모두 시도해보고 아래([2][1])가 틀렸다는 결론을 내린 후가 될 것이다.
즉, 쥐는 가장 최근에 만난 지점부터 조사해야 한다.
따라서 이러한 상황에는 나중에 입력된 데이터가 가장 먼저 빠져나오는 스택이 적절하다.
구현하기
스택을 용도에 맞게 수정하기
이번에도 스택을 구현하는 과정은 생략한다. 해당 내용은 아래의 링크에서 확인할 수 있다.
[Data Structure] 스택(Stack) 구현하기 (새 창)
지난 번에 구현한 스택을 문제 상황에 맞게 수정해야 한다.
수정된 내용 중 가장 주목해야할 부분은 스택의 데이터 입출력 방식이다. 지난 번과 달리 이번엔 스택의 데이터를 동적 할당하여 저장한다.
DataType.h
#pragma once
#define TRUE 1
#define FALSE 0
typedef struct Element { // 배열 요소의 자료형 정의
int row; // 행
int col; // 열
} Element;이 문제에서 자료 구조를 사용하는 목적은 지나갈 수 있는 근처 칸의 좌표를 저장하는데 있다. 칸마다 좌표는 2차원 배열 즉, 행과 열로 구성되므로 스택의 요소를 위와 같이 정의했다.
DynamicArray.c
DynamicArray.c 파일은 바뀐 부분만 소개한다.
Element* generateEmt(Element* e)
Element* generateEmt(Element* e)
{
Element* tmp = (Element*)malloc(sizeof(Element));
if (tmp != NULL) {
tmp->row = e->row;
tmp->col = e->col;
}
return tmp;
}새로운 함수의 등장이다. 스택의 데이터를 동적 할당하여 저장한다고 했는데, 바로 이 부분이 그것을 구현하는 코드이다. 이 함수는 저장하고자 하는 요소 e를 구성하는 모든 변수 row, col을 동적 할당 받은 변수 tmp에 복사하여 그 주소값을 반환하는 함수이다.
java에서 clone으로 객체를 복사하는 것과 유사하다.
int DAAdd(DynamicArray* darr, Element* e)
int DAAdd(DynamicArray* darr, Element* e)
{
if (DACheck(darr)) {
Element* tmp = generateEmt(e);
if (tmp == NULL) return FALSE;
darr->arr[++darr->index] = tmp;
return TRUE;
}
return FALSE;
}generateEmt() 함수에서 생성된 요소를 동적 배열에 추가하는 함수이다. 스택에서 이 함수를 호출하여 데이터를 저장할 것이다.
Stack.c
int StkStore(Stack* stack, Element* e, int maze[][6])
int StkStore(Stack* stack, Element* e, int maze[][6]) // 반환값 = 저장 성공 여부
{
if ((0 <= e->col && e->col < MAX) &&
(0 <= e->row && e->row < MAX) && (maze[e->row][e->col] != X)) {
if (stack != NULL && DAAdd(stack->darr, e)) {
stack->top++;
return TRUE;
}
}
return FALSE;
}스택에 데이터를 저장하는 함수이다. 매개 변수를 먼저 보면 미로를 나타내는 배열 maze가 전달된다. 그 이유는 스택에 저장하는 데이터는 '이동 가능한 칸'이고, 이동 가능한지 여부를 알기 위해선 배열에 접근이 가능해야 하기 때문이다.
if 문이 상당히 긴데, 스택에 저장되기 위해선 아래의 조건이 반드시 성립해야 하기 때문이다.
ⓐ 입력된 e의 좌표가 미로 밖으로 넘어가지 않는다.
ⓑ 입력된 e의 좌표가 이동할 수 없는 칸을 가리키지 않는다.
이 조건을 만족하면 StkStore() 함수는 DAAdd() 함수를 호출하여 Element의 사이즈만큼 메모리에서 동적 할당 받은 뒤에 요소 e의 row, col 값을 복사하여 그 주소값을 배열에 저장해준다.
int StkPop(Stack* stack, Element* e)
int StkPop(Stack* stack, Element* e)
{
if (StkIsEmpty(stack) != TRUE) { // Stack이 비어있지 않다면,
Element* tmp = DAGet(stack->darr, stack->top);
if (tmp != NULL) {
e->row = tmp->row;
e->col = tmp->col;
free(tmp);
stack->darr->arr[stack->top] = NULL;
stack->top--;
stack->darr->index--;
return TRUE;
}
}
return FALSE;
}스택에서 데이터를 꺼내오는 함수이다. 기존에는 꺼내온 데이터를 굳이 삭제하지 않고, 스택의 인덱스를 의미하는 변수 top을 감소시켜 top 이후의 데이터는 삭제된 것으로 취급하는 방식이었다. 그러나 스택의 데이터들이 동적 할당 받은 데이터로 수정되면서 이를 메모리에서 해제해주어야 메모리 누수를 방지할 수 있게 되었다.
main.c
전처리기
#include <stdio.h>
#include <stdlib.h>
#include "Stack.h"
#include "vld.h"
#define O 2 // 지나갈 수 있는 칸
#define X 3 // 지나갈 수 없는 칸
#define S 4 // 시작하는 칸 (Start)
#define E 5 // 끝나는 칸 (End)
#define MAX 6 // 미로의 최대 열 수필요한 라이브러리를 include 해준다.
또한 미로를 표현하기 위해 매크로 상수를 정의해주었다.
void mazeSearch(Stack* stack, int maze[][MAX]);
int findLocation(int maze[][MAX], int p, Element* e);미로의 출구를 찾는 함수 mazeSearch()이다. 찾는 과정을 출력하는 방향으로 작성하였기 때문에 return type은 void이다.
findLocation 함수는 입력된 칸을 탐색하는 함수이다.
예를 들어 findLocation(maze, S, e); 라고 한다면, 미로 maze에서 S 즉, 미로의 시작점을 찾아 e에 저장하는 방식이다. return value는 탐색 성공 여부를 의미한다.
이 함수가 필요한 이유는 어떤 미로가 주어져도 주어진 미로에서 시작점을 찾을 수 있게 하기 위함이다. 시작점을 찾아야 탐색을 시작할 위치를 지정할 수 있다.
main 함수
int main(void)
{
Stack* stack = StkCreate();
if (stack == NULL) return;
int maze[][6] = {
{X, X, X, X, X, X},
{S, O, O, O, O, X},
{X, O, X, O, X, X},
{X, X, X, O, O, E},
{X, X, X, X, X, X} };
mazeSearch(stack, maze);
StkDestroy(stack);
return 0;
}메인 함수는 간단하다. 스택과 미로를 선언하고 초기화해준다.
mazeSearch에 두 변수를 전달하면 미로를 찾는 과정을 출력한다.
이후엔 스택을 메모리에서 할당 해제해주고 함수를 종료한다.
mazeSearch(Stack* stack, int maze[][MAX])
이제 미로의 출구를 찾는 함수를 소개한다. 코드가 길어서 여러 번 끊어야 한다.
void mazeSearch(Stack* stack, int maze[][MAX])
{
Element* tmp = (Element*)malloc(sizeof(Element));
if (tmp == NULL) return;
if (!findLocation(maze, S, tmp)) return;
printf("현재 위치: maze[%d][%d]\n", tmp->row, tmp->col);
위에서 언급한 것처럼 미로를 탐색하기 위해서 시작할 지점을 찾아야 한다.
tmp라는 변수를 동적 할당 받아서 findLocation() 함수를 통해 시작점을 찾는다. 이 작업에 실패하면 함수를 종료시킨다.
변수 tmp는 이후에 이동 가능한 점을 불러와 임시로 저장할 때에도 사용된다.
while문 ①
while (maze[tmp->row][tmp->col] != E) { // 끝나는 지점이 나올 때까지 반복
maze[tmp->row][tmp->col] = X; // 현재 위치를 방문한 것으로 표시
Element e1 = { tmp->row, tmp->col + 1 };
StkStore(stack, &e1, maze);
Element e2 = { tmp->row, tmp->col - 1 };
StkStore(stack, &e2, maze);
Element e3 = { tmp->row + 1, tmp->col };
StkStore(stack, &e3, maze);
Element e4 = { tmp->row - 1, tmp->col };
StkStore(stack, &e4, maze);while 문의 종료 조건은 현재 위치 tmp가 E 즉, 미로의 출구와 같은지 여부이다.
위에서 변수 tmp가 스택에 저장된 '이동 가능했던 위치'를 불러와 저장할 때 사용된다고 했는데, 불러온 이동 가능한 위치가 곧 현재 위치가 된다.
현재 위치가 출구가 아니라면, 우선 현재 위치를 방문했다는 의미로 tmp가 가리키는 위치에 X를 대입한다. (이 방법은 이 순간에 미로를 손상시킨다. 미로를 손상시키지 않으려면 미로의 자료형을 int형이 아니라 방문했는지 여부도 포함하는 자료형을 정의하여 작성하면 된다. 하지만 그렇게 되면 미로를 선언할 때 가독성이 매우 떨어지므로 그렇게 하지 않았다.)
while문 ②
printf("현재 스택 상태:\n");
StkPrint(stack);
printf("\n");
if (StkPop(stack, tmp))
printf("현재 위치: maze[%d][%d]\n", tmp->row, tmp->col);
else {
printf("출구를 찾을 수 없습니다.\n");
break;
}
}
printf("출구에 도달하여 탐색을 종료합니다.\n");
free(tmp);
}스택을 관찰하기 위해 StkPrint() 함수를 사용하였다.
다음 칸으로 이동하기 위해 StkPop() 함수로 스택에 저장된 요소를 불러온다.
스택에서 요소를 불러오는데 성공했다면 그 칸으로 바로 이동한 셈이 된다. 따라서 현재 위치를 출력한다.
도착하지도 않았는데 더 이상 이동할 칸이 존재하지 않으면 출구를 찾을 수 없다는 메시지를 출력하고 반복문을 종료한다. 바로 함수를 종료하면 메모리 누수가 발생한다.
int findLocation(int maze[][MAX], int p, Element* e)
int findLocation(int maze[][MAX], int p, Element* e)
{
for (int i = 0; i <MAX; i++)
for (int j = 0; j < MAX; j++)
if (maze[i][j] == p) {
e->row = i;
e->col = j;
return TRUE;
}
return FALSE;
}2차원 배열을 탐색하여 입력된 p를 찾는다. (본 프로그램에서 p는 S로만 쓰였기에 p를 굳이 선언할 필요 없이 S를 찾는 목적으로만 작성할 수 있었다. 하지만 E가 존재하는지 등도 유효한 미로인지 알 수 있는 부분이므로 다른 목적으로도 사용할 수 있게끔 매개 변수 p를 선언했다.)
아쉬웠던 점
기존에 스택을 만들 때 메모리와 처리 시간의 효율성을 고려하여 데이터를 모두 포인터 형식으로 저장하게끔 했다.
그런데 mazeSearch() 함수에서 반복문을 사용할 때 변수 tmp에 임시로 저장하는 방식으로 진행하다보니 tmp의 주소값을 넘겨 스택의 요소가 '가리키도록' 됐고, 반복문의 다음 단계로 넘어가 tmp의 값이 다른 값으로 바뀌면서 스택에 저장된 값 또한 바뀌게 되는 문제가 생겼다.
이를 해결하기 위해 스택에 요소를 저장할 때 요소를 동적 할당하여 값을 복사하여 저장하는 일이 발생한 것이다.
이렇게 값을 복사하고 있자니 그럴꺼면 처음부터 배열도 이중 포인터로 선언하지 않고, 매개 변수도 포인터가 아니라 구조체 자체를 전달했어야 하나 싶었다.
그렇게만 해결할 수 있는 부분이 아닐텐데 다음 번에 큐를 만들 때 해결 방법을 찾아봐야겠다.
