C++ [수업정리] - 15주차

너비 우선 탐색 vs 깊이 우선 탐색

• 너비 우선 탐색

  • 큐

  • h만큼의 깊이로 내려 갔을 경우 메모리 사용량이 O(2^h)

    • 메모리 사용량이 크다.

  • 최단 거리를 보장한다.

• 깊이 우선 탐색

  • 스택

  • h만큼의 깊이로 내려 갔을 경우 메모리 사용량이 O(h)

    • 메모리 사용량이 작다.

  • 최단 거리를 보장하지 못한다.

📌단순한 질문에 겁먹으면 단순한 해결법을 보지 못한다.

• 즉 막연한 두려움으로 뒷걸음 치면 할 수 있는 것도 못하게 된다.

베이컨의 법칙

출처

케빈베이컨의 6단계 법칙( The Six Degrees of Kevin Bacon)이란 인간관계는 6단계만 거치면 지구상 대부분의 사람과 연결될 수 있다는 사회 이론이다.

사실 이 이론은 1976년 하버드 대학 교수 스탠리밀그램(Stanley Milgram)은 '6단계 분리이론(6 degrees of Separation)'을 발표하였고, 네트워크 이론의 시발점이 되었다.

1994년 Albright Univ.(올브라이트 대학)의 세 학생은 이 이론을 이용하여할리우드의 영화배우 케빈 베이컨과 같이 출연하지 않은 영화인들도 두세 단계를 거치면 케빈 베이컨과 관련을 맺게 된다는 일종의 게임을 만들었는 데 이것이 바로 The Six Degrees of Kevin Bacon게임이다.
이 법칙의 조건은 이 법칙의 연결다리는 "서로가 서로의 존재를 알고있는 상태일 것." 이라는 조건이 붙어야한다. 내쪽에서 유명 연예인을 알고있다 한들 그 연예인이 나를 모르기 때문에 '내가 알고있다'고 해서 나와 그 연예인과 다이렉트로 1단계로 연결시킬 수는 없다는 말이다. 여기서 말하는 '알고있다'는 기준이 반드시 얼굴, 이름 등 실존하는 신상정보일 필요는 없다. 가령 인터넷을 통해 알게된 사이이며 오로지 인터넷으로만 교류하여 실제 얼굴이나 이름을 모른다 하더라도 서로의 존재를 서로가 각인하고 있는 상태기 때문에 인정된다.

결국 중요한건 그 사람을 최소한 '서로 알고있는 사람'이라고 부를 수 있을 정도의 관계는 되야한다는 점이다.

마이크로소프트(MS)가 지난 2006년 조사에서 무작위로 추출한 한 쌍의 사람들이 평균 6.6명을 거치면 서로 연결된다고 밝히면서 케빈 베이컨의 6단계 법칙은 사실로 증명됐다.

Maze BFS

상속 friendly 하게 처음부터 개발을 진행하면 유연하게 니즈를 대처할 수 있다.

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <fstream>
#include <list>

using namespace std;

class Maze {
protected :
	int row, col;
	int crow, ccol;
	char direction;
	vector<vector<char>> map;
	void readMap(const char* name);
	bool isDone();
	void move();
	void mark(int r, int c);
	void getNextPositions(int &f1_r, int &f1_c, int &f2_r, int &f2_c);
	void turn(bool clockwise);
public :
	void play(const char* name);
	friend ostream& operator<<(ostream& output, const Maze& m);
};

class Position {
	int row, col;
	Position* prev;
public :
	Position(int r, int c, Position* p);
	void getRC(int& r, int& c);
	Position* getPrev();
};

Position::Position(int r, int c, Position* p) { row = r; col = c; prev = p; }
Position* Position::getPrev() { return prev; }
void Position::getRC(int& r, int& c) { r = row; c = col; }

class BFSMaze : public Maze {
	list<Position*> q;
	list<Position*> o;
	Position* find();
	void trace(Position* p);
	void open(Position* p);
	bool addable(int r, int c);
public :
	~BFSMaze();
	void play(const char* name);
	friend ostream& operator<<(ostream& output, const BFSMaze& m);
};

BFSMaze::~BFSMaze() {
	list<Position*>::iterator it, itt;
	for (it = q.begin(); it != q.end();) {
		itt = it;
		++it;
		delete (*itt);
	}
	for (it = o.begin(); it != o.end();) {
		itt = it;
		++it;
		delete (*itt);
	}
}

Position* BFSMaze::find() {
	Position* p;
	Position* t;
	int r, c;
	p = new Position(crow, ccol, NULL);
	q.push_back(p);
	while (!q.empty()) {
		t = q.front();
		q.pop_front();
		o.push_back(t);
		t->getRC(r, c);
		if (map[r][c] == 'x')
			return t;
		else
			open(t);
	}
	return NULL;
}
void BFSMaze::open(Position* p) {
	int r, c;
	int nr, nc;
	p->getRC(r, c);

	nr = r + 1; nc = c;
	if (addable(nr, nc)) q.push_back(new Position(nr, nc, p));

	nr = r - 1; nc = c;
	if (addable(nr, nc)) q.push_back(new Position(nr, nc, p));

	nr = r; nc = c - 1;
	if (addable(nr, nc)) q.push_back(new Position(nr, nc, p));

	nr = r; nc = c + 1;
	if (addable(nr, nc)) q.push_back(new Position(nr, nc, p));

}
bool BFSMaze::addable(int r, int c) {
	// 1. 경계를 벗어나는가?
	// 2. 벽인가?
	// 3. 이미 방문한 위치인가?
	if (r < 0 || r >= row || c < 0 || c >= col) return false;
	if (map[r][c] == '#') return false;

	list<Position*>::iterator it;
	int tr, tc;
	for (it = q.begin(); it != q.end(); ++it) {
		(*it)->getRC(tr, tc);
		if (tr == r && tc == c) return false;
	}
	for (it = o.begin(); it != o.end(); ++it) {
		(*it)->getRC(tr, tc);
		if (tr == r && tc == c) return false;
	}

	return true;
}

void BFSMaze::trace(Position* p) {
	int r, c;
	do {
		p->getRC(r, c);
		mark(r, c);
		p = p->getPrev();
	} while (p != NULL);
}


void BFSMaze::play(const char* name) {
	readMap(name);
	Position* final;
	final = find();
	trace(final);
}

ostream& operator<<(ostream& output, const BFSMaze& m) {
	return output << (Maze&)m;
}

void Maze::getNextPositions(int& f1_r, int& f1_c, int& f2_r, int& f2_c) {
	switch (direction) {
	case 'n':
		f1_r = crow - 1; f1_c = ccol; f2_r = crow - 1; f2_c = ccol + 1;
		break;
	case 's':
		f1_r = crow + 1; f1_c = ccol; f2_r = crow + 1; f2_c = ccol - 1;
		break;
	case 'e':
		f1_r = crow; f1_c = ccol + 1; f2_r = crow + 1; f2_c = ccol + 1;
		break;
	case 'w':
		f1_r = crow; f1_c = ccol - 1; f2_r = crow - 1; f2_c = ccol - 1;
		break;
	}
}
void Maze::turn(bool clockwise) {
	switch (direction) {
	case 'n':
		if (clockwise) direction = 'e'; else direction = 'w';
		break;
	case 's':
		if (clockwise) direction = 'w'; else direction = 'e';
		break;
	case 'e':
		if (clockwise) direction = 's'; else direction = 'n';
		break;
	case 'w':
		if (clockwise) direction = 'n'; else direction = 's';
		break;
	}
}
void Maze::mark(int r, int c) {
	if (map[r][c] == '.') map[r][c] = '*'; 
	else if (map[r][c] == '*') 
		map[crow][ccol] = '.';
}  
   
void Maze::move() {
	int f1_r, f1_c, f2_r, f2_c;
	getNextPositions(f1_r, f1_c, f2_r, f2_c);
	if (map[f1_r][f1_c] != '#' && map[f2_r][f2_c] == '#') {
		mark(f1_r, f1_c);
		crow = f1_r;
		ccol = f1_c;
	} else if (map[f1_r][f1_c] == '#' && map[f2_r][f2_c] == '#') {
		turn(false);
	} else {
		mark(f1_r, f1_c);
		crow = f1_r;
		ccol = f1_c;
		mark(f2_r, f2_c);
		turn(true);
		crow = f2_r;
		ccol = f2_c;
	}
}
bool Maze::isDone() {
	if (map[crow][ccol] == 'x') return true; else return false;
}

void Maze::readMap(const char* name) {
	ifstream ifs(name);
	ifs >> row;
	ifs >> col;
	for (int i = 0; i < row; i++) {
		vector<char> arow;
		for (int j = 0; j < col; j++) {
			char c;
			ifs >> c;
			arow.push_back(c);
			if (c == 's') { 
				crow = i; ccol = j; 
				if (i == 0) direction = 's';
				else if (j == 0) direction = 'e';
				else if (i == (row - 1)) direction = 'n';
				else direction = 'w';
			}
		}
		map.push_back(arow);
	}
}

void Maze::play(const char* name) {
	readMap(name);
	while (!isDone())
		move();
}

ostream& operator<<(ostream& output, const Maze& m) {
	for (int i = 0; i < m.row; i++) {
		for (int j = 0; j < m.col; j++) {
			output << m.map[i][j];
		}
		output << endl;
	}
	return output;
}

int main() {
	Maze mymaze;
	mymaze.play("map.txt");
	cout << mymaze << endl;

	BFSMaze mymaze2;
	mymaze2.play("map.txt");
	cout << mymaze2 << endl;
}