[SWEA] 1949. 등산로 조성

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

 

2019년 12월 27일 2시 30분부터 2문제 (등산로 조성과 수영장 문제)를 시도해보았습니다. 이번에 선택된 문제들은 상대적으로 쉬운 문제들이라 5시가 되기 전에 풀 수 있었습니다. 

 

 이번 문제도 아주 전형적인 dfs라고 볼 수 있습니다. 가장 높은 곳에서 시작하여 만들 수 있는 등산로중 가장 긴 등산로를 찾는 것이 문제입니다. 또 하나의 특징은 한 지점을 선택하여 최대 k만큼 산을 깎을 수 있다는 것입니다. 물론 깎지 않아도 무방합니다. 저는 무식한 방법을 택했습니다. 모든 지점을 0~k만큼 깎아보고 가장 높은 지점에서 시작하여 dfs로 가장 긴 등산로를 찾는 방법입니다. 가장 높은 지점은 최대 5곳이고 최대 k는 5이므로 시간 복잡도는 5 * 64 * 6 * O(dfs)입니다. 맵의 크기가 크지 않아 dfs에 오래 걸리지 않을 것이라고 판단하고 제출하였습니다.

 

 하지만 다른 제출 코드에 비해 많이 느리더군요. 빠르면 6 ~7ms 정도 걸리지만 제 코드는 100ms가 넘습니다. 좀 더 시간 단축을 시킬 수 있는 여지가 있는 것 같습니다. 다른 분들의 코드를 분석하여 추가적인 내용을 업로드하겠습니다.

	#include<iostream>
	#include<vector>
	using namespace std;
	int n, K,tc, max_length, max_height;
	int map[8][8];
	bool visited[8][8];
	int dy[4] = { 1,0,-1,0 };
	int dx[4] = { 0,1,0,-1 };
	struct Point
	{
	int y, x;
	};
	vector<Point> vt;
	void set_map_false()
	{
	for (int i = 0; i < n; i++)
	{
	for (int j = 0; j < n; j++)
	{
	visited[i][j] = false;
	}
	}
	}
	bool InRange(int y, int x)
	{
	return 0 <= x && x < n && 0 <= y && y < n;
	}
	void dfs(int y, int x, int length)
	{
	if (length > max_length)
	max_length = length;
	for (int i = 0; i < 4; i++)
	{
	int yy = y + dy[i];
	int xx = x + dx[i];
	if (InRange(yy, xx) && !visited[yy][xx])
	{
	if (map[y][x] > map[yy][xx])
	{
	visited[yy][xx] = true;
	dfs(yy, xx, length + 1);
	visited[yy][xx] = false;
	}
	}
	}
	}
	int main(void)
	{
	cin >> tc;
	for (int t = 1; t <= tc; t++)
	{
	cin >> n >> K;
	max_length = 0;
	max_height = 0;
	vt.clear();
	for (int i = 0; i < n; i++)
	{
	for (int j = 0; j < n; j++)
	{
	cin >> map[i][j];
	if (map[i][j] > max_height)
	max_height = map[i][j];
	}
	}
	for (int i = 0; i < n; i++)
	{
	for (int j = 0; j < n; j++)
	{
	if (max_height == map[i][j])
	vt.push_back({ i,j });
	}
	}
	for (int k = 0; k <= K; k++)
	{
	for (int i = 0; i < n; i++)
	{
	for (int j = 0; j < n; j++)
	{
	map[i][j] -= K;
	for (int p = 0; p < vt.size(); p++)
	{
	set_map_false();
	visited[vt[p].y][vt[p].x] = true;
	dfs(vt[p].y, vt[p].x, 1);
	}
	map[i][j] += K;
	}
	}
	}
	cout << '#' << t << ' ' << max_length << '\n';
	}
	}

view raw [SWEA] 1949.cpp hosted with ❤ by GitHub