[자료구조] C++로 쉽게 풀어쓴 자료구조 : 7장, 순환

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 7장. 순환

이번장은 재귀, 순환에 대하여 배웠다. 사실 재귀는 친숙하면서도 새로운 개념이다. 이전에도 재귀를 사용해 미로 찾기, 하노이탑 등등 몇가지 문제들을 접한적이 있는데, 이번시간에도 다시 점검한다는생각으로 배웠다. 간단하게 미로찾기 코드정도만 올려야 겠다.

 

교제와 다른 방식으로 구현한 미로찾기

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 8;

const int PATHWAY = 0;
const int WALL = 1;
const int BLOCKED = 2;
const int PATH = 3;

int maze[N][N] = {
	{0,0,0,0,0,0,0,1},
	{0,1,1,0,1,1,0,1},
	{0,0,0,1,0,0,0,1},
	{0,1,0,0,1,1,0,0},
	{0,1,1,1,0,0,1,1},
	{0,1,0,0,0,1,0,1},
	{0,0,0,1,0,0,0,1},
	{0,1,1,1,0,1,0,0}
};

void printMaze() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << maze[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

bool findPath(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= N || maze[x][y] != PATHWAY)
		return false;
	else if (x == N - 1 && y == N - 1) {
		maze[x][y] = PATH;
		return true;
	}
	else {
		maze[x][y] = PATH;
		if (findPath(x-1, y) || findPath(x, y + 1) || findPath(x + 1, y) || findPath(x, y - 1))
			return true;
		maze[x][y] = BLOCKED;
		return false;
	}
}

int main()
{
	printMaze();
	findPath(0, 0);
	printMaze();

    return 0;
}

 

결과는 다음과 같다.

올바른 경로를 따라서 길을 찾아갔다.

 

---

2) 나의 현황

◆ 간단히 재귀에 대한 내용을 복습하였다. 추가로 파이썬으로 Flask를 사용하여 웹페이지를 만들어보고있다. 구현이 완료되면 올려볼 예정이다.