Grotesque Maze 풀기 전 기초 개념 다지기

아래의 코드는 백 트래킹 코드이다.

정확한 원리를 이해하기 위해서 코드는 책을 참고하였다.  

언제 사두었는지 모르겠으나, 사두고 읽지 않고 벽에 박혀있는 책이었다. 종종 읽으면서 머릿속에 좋은 내용을 더 담아야겠다.

[책] : 뇌를 자극하는 알고리즘 

백 트래킹 요약 : 

1. 해가 하나 이상 존재한다. 

2. 여러개의 부분 문제를 통해 부분 해를 구하다보면 어느순간 탈출 해를 구할 수 있다. 

[이해도를 높이기 위한 상황 부여] : ep01. 초보운전자의 초행길 가는 날

[부분 문제] : 두 갈랫길이 눈앞에 있을 때 우측으로 갈지, 좌측으로 갈지 고민하는 상황

[부분 해] : 부분 문제에 대한 해결책 

즉, 운전자가 우측으로 가야된다는 것을 인지하고, 우측으로 가게 되는 상황

[탈출 해] : 초보 운전자가 네비게이션을 키고 여러 고민 끝에 마침내 원하는 목적지에 도달한 상황

공부를 하며 느낀 점 : 백 트래킹은 나에게 괜찮은 자극제가 되었다. Pwnable.kr의 Maze는 백 트래킹으로 풀지 않을 것이다. 이미 시나리오는 구상 중인 상태고, 될 것 같다는 자신감이 든다. 

자신감이 들었었는데, 백 트래킹을 하지 않으니 1단계도 못 깰 것 같다. 

랜덤으로 키 값을 받아서 Server에 패킷을 보내게 해두었는데 s를 보냈다가 w를 보내게 되면 다시 원점으로 돌아가버린다.><;; 백트래킹으로 진행하다가 특별한 상황때만 돌아가게 해보자.

하지만, 단계가 지날 때 마다 출현하는 수 많은 장애물을 어떻게 우회하면 효율적인지 아직은 모르겠다. 며칠 더 지나봐야 생각이 날 것 같다. 

백 트래킹을 이용하여 스도쿠도 구현 할 수 있다고 하니 스도쿠도 머지않아 구현해보아야겠다. 

알고리즘에 대해 조금 더 많은 관심을 가져야겠다.

[테스트 코드]

#include <stdio.h>

#include "MageSolver.h"

int main(int argc, char*argv[])

{

// 파일은 매개변수로 불러올 것임

int i, j = 0;

MazeInfo Maze;

if (argc < 2)

{

printf("Usage: MazeSolver <MazeFile>\n");

return 0;

}

// 매개변수로 불러온 파일을 fopen함수로 열다가 실패하게 되면 FAIL이 반환되게 해둠 

if (GetMaze(argv[1], &Maze) == FAIL)

return 0;

if (Solve(&Maze) == FAIL)

return 0;

for (i = 0; i < Maze.RowSize; i++)

{

for (j = 0; j < Maze.ColumnSize; j++)

{

printf("%c", Maze.Data[i][j]);

}

printf("\n");

}

return 0;

}

[헤더파일]

#pragma once

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_BUFFER 1024

#define INIT_VALUE -1

#define START  'S' // 시작

#define GOAL  'G' // 탈출

#define WAY  ' '

#define WALL '#'

#define MARKED '+' 

// 북, 남, 동, 서 

enum DIRECTION { NORTH, SOUTH, EAST, WEST };

enum RESULT { FAIL, SUCCEED };

// 미로의 정보와 미로의 좌표는 별개로 정의 

typedef struct tagPosition

{

int X;

int Y;

}Position;

typedef struct tagMazeInfo

{

int ColumnSize;

int RowSize;

char **Data;

}MazeInfo;

int Solve(MazeInfo* Maze);

int MoveTo(MazeInfo* Maze, Position* Current, int Direction);

int GetNextStep(MazeInfo* Maze, Position* Current, int Direction, Position* Next);

int GetMaze(char* FilePath, MazeInfo* Maze);

[MazeSolver.c]

#include "MageSolver.h"

int Solve(MazeInfo* Maze)

{

int i = 0;

int j = 0;

int StartFound = FAIL;

int Result = FAIL;

Position Start;

for (i = 0; i < Maze->RowSize; i++)

{

for (j = 0; j < Maze->ColumnSize; j++)

{

if (Maze->Data[i][j] == START)

{

Start.X = j;

Start.Y = i;

StartFound = SUCCEED;

break;

}

}

}

if (StartFound == FAIL)

return FAIL;

//코드는 똑같은 기능을 할 땐 함수화 해두는 것이 아주 좋다.

if (MoveTo(Maze, &Start, NORTH)) // 북쪽 방향 이동 

Result = SUCCEED;

if (MoveTo(Maze, &Start, SOUTH))

Result = SUCCEED;

if (MoveTo(Maze, &Start, EAST))

Result = SUCCEED;

else if (MoveTo(Maze, &Start, WEST))

Result = SUCCEED;

Maze->Data[Start.Y][Start.X] = START;

return Result;

}

int MoveTo(MazeInfo *Maze, Position *Current, int Direction)

{

int i = 0;

// 데이터 관리 효율을 위해 배열에 좌표를 선언하였다

int Dirs[] = { NORTH, SOUTH, WEST, EAST };

Position Next;

// 미로의 데이터의 좌표가 목적지랑 일치하게 되면 

// 비로소 성공을 반환한다 

if (Maze -> Data[Current->Y][Current->X] == GOAL)

return SUCCEED;

Maze->Data[Current->Y][Current->X] = MARKED;

for (i = 0; i < 4; i++)

{

if (GetNextStep(Maze, Current, Dirs[i], &Next) == FAIL)

{

continue;

}

if (MoveTo(Maze, &Next, NORTH) == SUCCEED)

return SUCCEED;

}

Maze->Data[Current->Y][Current->X] = WAY;

return FAIL;

}

int GetNextStep(MazeInfo*Maze, Position *Current, int Direction, Position* Next)

{

switch (Direction)

{

// 북쪽이라면, 현재 Current 에서 Y좌표가 하나 감소

case NORTH:

Next->X = Current->X;

Next->Y = Current->Y - 1;

// 북쪽으로 쭉 가다가 -1을 만나면 

if (Next->Y == -1)

return FAIL;

break;

case SOUTH:

Next->X = Current ->X;

Next->Y = Current->Y+1;

// 남쪽으로 쭉 가다가 RowSize를 만나면 (제일 밑에까지 내려가게 되면, 기존에 세팅 된 행 갯수일거임)

if (Next->Y == Maze->RowSize)

return FAIL;

break;

case EAST:

Next->X = Current->X + 1;

Next->Y = Current->Y;

// 동쪽으로 쭉 가다가 ColumnSize를 만나면

if (Next->X == Maze->ColumnSize)

return FAIL;

break;

case WEST:

Next->X = Current->X - 1;

Next->Y = Current->Y;

// 서쪽으로 가다가 -1을 만나면

if (Next->X == -1)

return FAIL;

break;

}

// 위의 SWITCH문에서 세팅 된 공간이 벽이나 이미 지나왔던 길이라면?

if (Maze->Data[Next->Y][Next->X] == WALL)

return FAIL;

if (Maze->Data[Next->Y][Next->X] == MARKED)

return FAIL;

// 저 위의 조건들이 다 아니면 "참"

return SUCCEED;

}

int GetMaze(char* FilePath, MazeInfo* Maze)

{

int i, j = 0;

int RowSize = 0;

int ColumnSize = INIT_VALUE; // 열 같은 경우는 초깃값을 -1로 해두는 구나 

FILE *fp;

char buffer[MAX_BUFFER];

if ((fp = fopen(FilePath, "r")) == NULL)

{

printf("Cannot open file : %s\n", FilePath);

return FAIL;

}

while (fgets(buffer, MAX_BUFFER, fp) != NULL)

{

RowSize++;

if (ColumnSize == INIT_VALUE)

{

ColumnSize = strlen(buffer) - 1;

}

else if (ColumnSize != strlen(buffer) - 1)

{

printf("Maze Data in file : %s is not valid. %d\n", FilePath, strlen(buffer));

fclose(fp);

return FAIL;

}

}

Maze->RowSize = RowSize;

Maze->ColumnSize = ColumnSize;

// 2차원 배열 동적할당

Maze->Data = (char**)malloc(sizeof(char*)* RowSize);

for (i = 0; i < RowSize; i++)

Maze->Data[i] = (char *)malloc(sizeof(char) * ColumnSize);

rewind(fp);

for (i = 0; i < RowSize; i++)

{

fgets(buffer, MAX_BUFFER, fp);

for (j = 0; j < ColumnSize; j++)

Maze->Data[i][j] = buffer[j];

}

fclose(fp);

return SUCCEED;

}