[자료구조] C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 5

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

DFS를 활용한 미로찾기

헤더파일에서는 using namespace std를 사용하지 않았습니다. 메인에서만 사용하였습니다. 헤더에서 이를 선언해버리면 이를 include하는 다른 소스파일에서까지 using namespace std가 적용되기때문에 헤더파일에서는 std::를 다 적어줬습니다.

 

Location2D.h

#pragma once

struct Location2D {
	int _row;
	int _col;
	Location2D(int row = 0, int col = 0) : _row(row), _col(col) {}
	bool isNeighbor(Location2D& p) {
		return ((_row == p._row && (_col == p._col - 1 || _col == p._col + 1))
			|| (_col == p._col && (_row == p._row - 1 || _row == p._row + 1)));
	}

	bool operator = (Location2D& p) { return _row == p._row && _col == p._col; }
};

 

 

Maze.h

#pragma once
#include <iostream>
#include <cstdio>
#include <fstream>
#include "Location2D.h"
#include <queue>

class Maze {
	int _width;
	int _height;
	int** _map;
	Location2D exitLoc;
    std::queue<Location2D> mapQue;
public:
	Maze() { init(0, 0); }
	~Maze() { reset(); }
	void init(int w, int h);
	void reset();
	void load(const char* fname);
	void print();
    bool isVaildLoc(const int& r, const int& c);
	void searchExit();
};

void Maze::init(int w, int h)
{
	_map = new int* [h];
	for (int i = 0; i < h; i++)
		_map[i] = new int[w];
}

void Maze::reset()
{
	for (int i = 0; i < _height; i++)
		delete[] _map[i];
	delete _map;
}

void  Maze::load(const char* fname) //파일에서 미로 파일을 읽어옴
{
    std::ifstream fin(fname, std::ios::in);
    fin >> _width >> _height;
    init(_width, _height);
    int temp;

    for (int i = 0; i < _height; i++)
    {
        for (int j = 0; j < _width; j++)
        {
            fin >> temp;
            _map[i][j] = temp;
            if (_map[i][j] == 5)
            {
                Location2D entry(j, i);
                mapQue.push(entry);
            }

            else if (_map[i][j] == 9)
            {
                exitLoc._col = i;
                exitLoc._row = j;
            }
        }
        std::cout << std::endl;
    }
    fin.close();
}

void Maze::print() {
    std::cout << "전체 미로의 크기 = " << _height << " * " << _width << std::endl;

    for (int i = 0; i < _height; i++) {
        for (int j = 0; j < _width; j++)
        {
            if (_map[i][j] == 1)
            {
                std::cout << "  ";
            }
            else if (_map[i][j] == 0)
            {
                std::cout << "■";
            }
            else if (_map[i][j] == 2)
            {
                std::cout << "□";
            }
            else if (_map[i][j] == 5)
            {
                std::cout << "○";
            }
            else if (_map[i][j] == 9)
            {
                std::cout << "◎";
            }
        }
        printf("\n");
    }
}

bool Maze::isVaildLoc(const int& r, const int& c)
{
    if (r < 0 || c < 0 || r >= _height || c >= _width) return false;
    else return _map[r][c] == 1 || _map[r][c] == 9;
}

void Maze::searchExit()
{
    while (!mapQue.empty())
    {
        Location2D here = mapQue.front();
        mapQue.pop();

        int r = here._row;
        int c = here._col;
        if (_map[r][c] == 9) return;
        else {
            _map[r][c] = 2;
            if (isVaildLoc(r - 1, c)) mapQue.push(Location2D(r - 1, c));
            if (isVaildLoc(r + 1, c)) mapQue.push(Location2D(r + 1, c));
            if (isVaildLoc(r, c - 1)) mapQue.push(Location2D(r, c - 1));
            if (isVaildLoc(r, c + 1)) mapQue.push(Location2D(r, c + 1));
        }
    }
}

 

 

main.cpp

#include "Maze.h"
using namespace std;

int main(void)
{

    Maze maze; //미로 탐색 객체 생성
    maze.load("Maze.txt");
    maze.print();
    maze.searchExit(); //미로를 탐색해 출구를 찾음
    cout << endl;
    maze.print();

    return 0;
}

 

결과는 다음과 같다.