[백준알고리즘] 2589번: 보물섬 -C++

[백준알고리즘] 2589번: 보물섬 -C++

2589번: 보물섬 (acmicpc.net)

2589번: 보물섬

문제를 봤을 때 브루트 포스인가? 단순히 최단거리는 못 구하는데? 일단 해보자! 했다. 예전에는 너무 최단거리 문제만 풀다가 브루트 포스 문제 여부를 감을 잡지 못했었는데, 지금 오히려 눈이 넓어졌나보다.

골드라고 해서 살짝 쫄았는데 정답 비율은 생각보다 높았다. 어쩐지 어렵진 않더라..

---

문제 풀이

문제는 브루트 포스 방식을 사용하면 된다. 그리고 그래프 탐색을 사용하면 된다.

 

모든 'L' 위치를 시작점으로 했을 때 가장 멀리 있는 'L'까지의 거리를 구한다. 그리고, 그 거리들 중에서 가장 긴 거리를 구하는 문제다.

 

이때 거리를 구하는 것은 DFS나 BFS를 사용하면 된다. 그런데, 예전에 거리 탐색 문제를 풀 때 DFS보다 BFS가 더 빠르다고 했다는 것이 기억났다.

BFS를 적용하려는데 오랜만에 해서 어떻게 했었는지 고민하느라 시간이 좀 걸리긴 했다. 그래서 예전에 사용하던 BFS 형태와는 조금 다르게 처리했을 수도 있다.

 

좀 더 함수화를 수행할 수 있을 것 같은데 피곤해서 자야겠다..

#include <cstdio>
#include <cstring>
#include <list>

#define POINT std::pair<int, int>

void inputMap();
int findLongDistanceOfShortestPath();
int findLongDistanceUsingBFS(int ppDistanceMap[][51]);
void reservePoint(int ppDistanceMap[][51], const POINT &point, const int iDistance);
void registerNextBFS(const POINT &point, const int iDistance);

void copyMap(int ppClone[][51]);
void initMap(int ppClone[][51]);

int ppMap[51][51] = { 0, };
int ppCloneMap[51][51] = { 0, };
int ppVisitMap[51][51] = { 0, };

std::list<POINT> lstQueue;

int main(void) {
	inputMap();

	int iDistance = findLongDistanceOfShortestPath();

	printf("%d", iDistance - 1);

	return 0;
}

void inputMap() {
	int iHeight = 0;
	int iWidth = 0;

	scanf("%d %d", &iHeight, &iWidth);

	::memset(ppMap, -1, sizeof(int) * 51 * 51);

	for ( int i = 1; i <= iHeight; ++i ) {
		for ( int j = 1; j <= iWidth; ++j ) {
			char cSquare = 0;
			scanf(" %c", &cSquare);

			if ( 'L' == cSquare ) {
				ppMap[i][j] = 0;
			}
			else if ( 'W' == cSquare ) {
				ppMap[i][j] = -1;
			}
			else {
				// nothing
			}
		}
	}
}

int findLongDistanceOfShortestPath() {
	int iLongest = 0;

	for ( int i = 1; i <= 50; ++i ) {
		for ( int j = 1; j <= 50; ++j ) {
			if ( 0 != ppMap[i][j] ) {
				continue;
			}

			copyMap(ppCloneMap);

			POINT point = std::make_pair(i, j);
			registerNextBFS(point, ppMap[i][j]);

			int iDistance = findLongDistanceUsingBFS(ppCloneMap);
			iLongest = (iLongest < iDistance) ? iDistance : iLongest;
		}
	}

	return iLongest;
}

int findLongDistanceUsingBFS(int ppDistanceMap[][51]) {
	int iLongest = 0;

	while ( false == lstQueue.empty() ) {
		const int &iHeight = lstQueue.front().first;
		const int &iWidth = lstQueue.front().second;

		const int iCurrentDistance = ppDistanceMap[iHeight][iWidth];
		iLongest = (iLongest < iCurrentDistance) ? iCurrentDistance : iLongest;

		reservePoint(ppDistanceMap, std::make_pair(iHeight - 1, iWidth), iCurrentDistance);
		reservePoint(ppDistanceMap, std::make_pair(iHeight + 1, iWidth), iCurrentDistance);
		reservePoint(ppDistanceMap, std::make_pair(iHeight, iWidth - 1), iCurrentDistance);
		reservePoint(ppDistanceMap, std::make_pair(iHeight, iWidth + 1), iCurrentDistance);

		lstQueue.pop_front();
	}

	return iLongest;
}

void reservePoint(int ppDistanceMap[][51], const POINT &point, const int iDistance) {
	const int &iHeight = point.first;
	const int &iWidth = point.second;

	if ( iHeight < 1 || 50 < iHeight ) {
		return;
	}
	if ( iWidth < 1 || 50 < iWidth ) {
		return;
	}
	if ( 0 != ppDistanceMap[iHeight][iWidth] ) {
		return;
	}

	registerNextBFS(std::make_pair(iHeight, iWidth), iDistance);
}

void registerNextBFS(const POINT &point, const int iCurrentDistance) {
	ppCloneMap[point.first][point.second] = iCurrentDistance + 1;
	lstQueue.push_back(point);
}

void copyMap(int ppClone[][51]) {
	::memcpy(ppClone, ppMap, sizeof(int) * 51 * 51);
}

void initMap(int ppClone[][51]) {
	::memset(ppClone, 0, sizeof(int) * 51 * 51);
}