[백준] 2178 - 미로 탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

• 미로 탐색의 과정에서 최단 거리를 구하는 문제 -> BFS
• 인접 행렬을 사용하여 해결을 할려고 하니 메모리 초과가 나온다. (답은 출력됨)
• 미로의 입력의 경우 배열을 이용[101][101]하여 사용하였고 std::vector<>와 std::find()를 이용하여 방문여부를 검사하니 메모리 초과는 나오지 않으나 68m의 시간이 걸렸다. 채점현황에서 0ms가 소비되는 코드가 많은 것을 보아 효율을 높일 수 있는 (?) 코드로 수정이 필요하다.

---

• 코드

#include <iostream>
#include <queue>
#include <algorithm>

// def
#define BOARD_MAX_SIZE 100
#define POS_PAIR std::pair<int, int>
#define SCORE_PAIR std::pair<POS_PAIR, int>

// struct
struct DATA 
{
	DATA()
	{
		data = 0;
	}
	int data;
};

// global
DATA board[BOARD_MAX_SIZE + 1][BOARD_MAX_SIZE + 1];
int direction[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // 상, 하, 좌, 우

// method
bool CheckingValid(int x, int y, int X, int Y);
int BFS(DATA board[][BOARD_MAX_SIZE + 1], int X, int Y);

int main()
{
	// 2178 - 미로탐색
	std::ios::sync_with_stdio(false);

	// input
	int N, M;
	N = M = 0;
	(void)scanf("%d %d", &N, &M);

	for (int n = 0; n < N; n++)
	{
		for (int m = 0; m < M; m++)
		{
			int input = 0;
			(void)scanf("%1d", &input);

			board[n][m].data = input;
		}
	}

	// calc
	int answer = BFS(board, N, M);

	// print
	printf("%d", answer);

	return 0;
}

bool CheckingValid(int x, int y, int X, int Y)
{
	bool retValue = true;

	if ((x < 0 || x >= X) || (y < 0 || y >= Y))
		retValue = false;

	return retValue;
}


int BFS(DATA board[][BOARD_MAX_SIZE + 1], int X, int Y)
{
	int retValue = 0;

	// calc
	std::queue<SCORE_PAIR> que;
	std::vector<POS_PAIR> visistd;
	que.push(SCORE_PAIR(POS_PAIR(0,0), 1));

	while (!que.empty())
	{
		SCORE_PAIR curPos = que.front();
		que.pop();
		int curX = curPos.first.first;
		int curY = curPos.first.second;
		int score = curPos.second;

		if (curX == X - 1 && curY == Y - 1)
		{
			retValue = score;
			break;
		}
			
		for (int d = 0; d < 4; d++)
		{
			int nearX = curX - direction[d][0];
			int nearY = curY - direction[d][1];

			const bool bIsValid = CheckingValid(nearX, nearY, X, Y);
			std::vector<POS_PAIR>::iterator findIter = std::find(visistd.begin(), visistd.end(), POS_PAIR(nearX, nearY));
			if (true == bIsValid && visistd.end() == findIter)
			{
				if (1 == board[nearX][nearY].data)
				{
					que.push(SCORE_PAIR(POS_PAIR(nearX, nearY), score+1));
					visistd.push_back(POS_PAIR(nearX, nearY));
				}
			}
			else
				continue;
		}
	}

	return retValue;
}

---

• 미로를 입력받는 배열의 자료형을 int -> char 로 변경하여 0ms 시간으로 해결하였다.
• int 4 byte, char 1 byte의 크기를 고려하지 않고 해결방법을 생각하였던게 큰 실수 였다.
• 코드

#include <iostream>
#include <cstring>
#include <queue>

// def
#define BOARD_MAX_SIZE 100
#define POS_PAIR std::pair<int, int>
#define SCORE_PAIR std::pair<POS_PAIR, int>

// global
char board[BOARD_MAX_SIZE + 1][BOARD_MAX_SIZE + 1];
bool visited[BOARD_MAX_SIZE + 1][BOARD_MAX_SIZE + 1];
int direction[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // 상, 하, 좌, 우

// method
bool CheckingValid(int x, int y, int X, int Y);
int BFS(char board[][BOARD_MAX_SIZE + 1], int X, int Y);

int main()
{
	// 2178 - 미로탐색
	std::ios::sync_with_stdio(false);

	// input
	int N, M;
	N = M = 0;
	(void)scanf("%d %d", &N, &M);

	//printf("%d %d\n\n", sizeof(char), sizeof(int));

	for (int n = 0; n < N; n++)
	{
		char buf[BOARD_MAX_SIZE + 1] = { '\0', };
		(void)scanf("%s", buf);
		memcpy(board[n], buf, strlen(buf));
	}

	// calc
	int answer = BFS(board, N, M);

	// print
	printf("%d", answer);

	return 0;
}

bool CheckingValid(int x, int y, int X, int Y)
{
	bool retValue = true;

	if ((x < 0 || x >= X) || (y < 0 || y >= Y))
		retValue = false;

	return retValue;
}


int BFS(char board[][BOARD_MAX_SIZE + 1], int X, int Y)
{
	int retValue = 0;

	// calc
	std::queue<SCORE_PAIR> que;
	que.push(SCORE_PAIR(POS_PAIR(0,0), 1));

	while (!que.empty())
	{
		SCORE_PAIR curPos = que.front();
		que.pop();
		int curX = curPos.first.first;
		int curY = curPos.first.second;
		int score = curPos.second;

		if (curX == X - 1 && curY == Y - 1)
		{
			retValue = score;
			break;
		}
		
		for (int d = 0; d < 4; d++)
		{
			int nearX = curX - direction[d][0];
			int nearY = curY - direction[d][1];

			const bool bIsValid = CheckingValid(nearX, nearY, X, Y);
			if (true == bIsValid && false == visited[nearX][nearY])
			{
				if ('1' == board[nearX][nearY])
				{
					que.push(SCORE_PAIR(POS_PAIR(nearX, nearY), score+1));
					visited[nearX][nearY] = true;
				}
			}
			else
				continue;
		}
	}

	return retValue;
}