[2021.04.03] 코딩테스트준비

DFS, BFS 예전에 만들어 놨던 틀보고 다시 한 번 연습해보기.

#include <vector>
#include <iostream>
#include <queue>

#define MAX_SIZE 10

using namespace std;

vector<vector<int>> maze = {
	{1,0,1,1,1,1},
	{1,0,1,0,1,0},
	{1,0,1,1,1,1},
	{1,1,1,0,1,1},
};

int numOfX = 6;
int numOfY = 4;

pair<int, int> startPos = { 0, 0 };
pair<int, int> endPos = { 5, 3 };

bool isVisit[MAX_SIZE][MAX_SIZE];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

vector<pair<int, int>> path;

bool isValidXY(int x, int y)
{
	if ((x < 0) || (y < 0) || (x >= numOfX) || (y >= numOfY))
		return false;
	return true;
}

void dfs(int x, int y)
{
	// 진입시 바로 할 일
	isVisit[x][y] = true;
	path.push_back({x, y});

	// 종료조건 + 종료시 처리할 것 goto
	if ((x == endPos.first) && (y == endPos.second)) {
		for (int i = 0; i < path.size(); i++) {
			cout << "[" <<path[i].first << "," << path[i].second << "]";
		}
		cout << endl;
		goto exit;
	}

	// 다음 노드 진입 및 가지치기
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		// vector<vector<int>> 의 경우 x,y가 아닌 y, x 순으로 접근 필요
		if (isValidXY(nx, ny) && (maze[ny][nx] == 1) && (isVisit[nx][ny] == false)) {
			dfs(nx, ny);
		}
	}

	// 종료시 처리할  것
exit:
	isVisit[x][y] = false;
	path.pop_back();
}

struct Pos {
	int x, y;
	int level;
};

void bfs(int x, int y)
{
	queue<Pos> q;
	q.push({ x, y, 1});
	// 진입시 바로 할 일
	isVisit[x][y] = true;

	while (!q.empty()) {
		Pos curPos = q.front();
		q.pop();

		// 종료조건
		if ((curPos.x == endPos.first) && (curPos.y == endPos.second)) {
			cout << curPos.level << endl;
			break;
		}

		// 다음 노드 진입 및 가지치기
		for (int i = 0; i < 4; i++) {
			int nx = curPos.x + dx[i];
			int ny = curPos.y + dy[i];
			// vector<vector<int>> 의 경우 x,y가 아닌 y, x 순으로 접근 필요
			if (isValidXY(nx, ny) && (maze[ny][nx] == 1) && (isVisit[nx][ny] == false)) {
				q.push({nx, ny, curPos.level + 1});
				// 집입시 바로 할 일
				isVisit[nx][ny] = true;
			}
		}
	}
}

int main()
{
	//dfs(0, 0);
	//bfs(0, 0);
	return 0;
}

#include <iostream>
#include <vector>

using namespace std;

vector<char> elements = { 'A', 'B', 'C', 'D' };
vector<char> path;

void dfs(int preIdx)
{
	// print path
	if (path.size() != 0) { // not include anything yet
		cout << path.size() << " : ";
		for (int i = 0; i < path.size(); i++) {
			cout << path[i] << " ";
		}
		cout << endl;
	}

	for (int i = preIdx + 1; i < elements.size(); i++) {
		path.push_back(elements[i]);
		dfs(i);
		path.pop_back();
	}
}

int main()
{
	dfs(-1);
	return 0;
}