Boj 1981) 배열에서 이동

문제

백준 1981

방법 1 (DP)

설명

처음 시도한 방법이다. 좌표와 경로의 최댓값을 dp[101*101][201] 로 사용했다. 크기가 선형이 아니므로 메모리 제약이 심했으면 불가능한 방법이며, 보통의 다이나믹 프로그래밍과 달리 이건 같은 dp[][] 의 인덱스라도 최적해가 여러번 업데이트 가능해 시간복잡도가 더 크다.

여러모로 장점을 찾을 수 없는 안좋은 방법이다.

시간 복잡도

O(\(N^2 \times 200^2\))

코드

int n;
int board[101 * 101];
int dp[101 * 101][201];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
bool Valid(int x, int y) { return x >= 0 && y >= 0 && x < n && y < n; }

struct P { int cur, max_v, min_v; };

void BFS(int start)
{
	fill(&dp[0][0], &dp[101*101][0], 1e9);
	queue<P> q;
	q.push({ start, board[start], board[start] });
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		if (dp[cur.cur][cur.max_v] <= cur.max_v - cur.min_v) continue;
		dp[cur.cur][cur.max_v] = cur.max_v - cur.min_v;

		for (int i = 0; i < 4; i++)
		{
			int x = cur.cur % n + dx[i];
			int y = cur.cur / n + dy[i];
			if (Valid(x, y))
			{
				int d = y * n + x;
				q.push({ d, max(cur.max_v, board[d]), min(cur.min_v, board[d]) });
			}
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n * n; i++)
		cin >> board[i];

	BFS(0);
	int ans = 1e9;
	for (int i = 0; i <= 200; i++)
		ans = min(ans, dp[n * n - 1][i]);	
	cout << ans;
}

방법 2 (투포인터)

설명

전략은 간단하다.

1. 탐색 시 특정 범위만 하도록 제약한다.
2. 범위는 투포인터로 찾는다.

시간 복잡도

O(\(N^2 M\))

• 여기서 \(M\) 은 Input 으로 들어오는 수의 범위로 200 이 해당된다.

코드

int n;
int board[101 * 101], min_v = 1e9, max_v = -1;
bool visitTB[101 * 101];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
bool Valid(int x, int y) { return x >= 0 && y >= 0 && x < n&& y < n; }

bool BFS(int l, int r)
{
	fill(visitTB, visitTB + n * n, 0);
	queue<int> q;
	if (board[0] > r || board[0] < l) return false;
	q.push(0);
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		for (int i = 0; i < 4; i++)
		{
			int x = cur % n + dx[i], y = cur / n + dy[i];
			int d = y * n + x;
			if (Valid(x, y) && board[d] <= r && board[d] >= l && !visitTB[d])
			{
                visitTB[d] = true;
				q.push(d);
			}
		}
	}
	return visitTB[n*n-1];
}

int main()
{
	cin >> n;
	for (int i = 0; i < n * n; i++)
	{
		cin >> board[i];
		min_v = min(min_v, board[i]);
		max_v = max(max_v, board[i]);
	}

	int ans = 1e9;
	int begin = min_v, end = min_v;
	while (begin <= end && end <= max_v)
	{
		bool r = BFS(begin, end);
		if (r) {
			ans = min(ans, end - begin);
			begin++;
		}
		else end++;
	}
	cout << ans;
}

방법 3 (이분탐색)

설명

구글링하면 보이는 잡다한 블로그에서 왜 이분탐색을 정해로 내놓는지 모르겠다. 거기서 사용하는 방법은 투포인터 방법보다 훨씬 느리고, 필요한 발상도 투포인터랑 이분탐색이랑 난이도 측면에서 크게 다르지 않기 때문이다. 숫자의 범위를 찾는 방법만 다를 뿐, 가장 핵심인 탐색 시에 특정 범위 내의 노드만 지나게 한다는 것은 똑같다. 그럼에도 대부분의 블로그가 비슷한 해답을 기록하는 것은 복제의 결과가 아닐지 의심된다.

그럼에도 이분탐색으로 풀 때 최적화를 한다면 투포인터만큼 혹은 그 이상으로 빠르다. 이때 필요한 최적화 부분은 두군데가 있다. 가능한 차이를 선택하는 이분탐색 시 사용되는 변수인 begin 과 end 가 첫번째고, 선택된 차이에 대한 모든 경우를 포문으로 노가다하는 부분인 TwoPtrs() 의 begin 과 end 가 두번째다. 최적화 전후가 어떻게 다른지는 아래 코드의 주석 부분을 참고하자.

시간복잡도

board[0][0] = board[n-1][n-1] = 100 이라고 생각해보자. 경로에는 시작점과 끝점이 반드시 포함되어야한다. 그러므로 가능한 경우의 수는 Dist<=100 이라면 Dist+1 이고, Dist>100 이면 200-Dist 이다. 만약에 board[0][0] != board[n-1][n-1] 이면 그 차이만큼 가능한 경우의 수가 더 줄어들 것이고, 0~200 중에 가운데가 아니라 구석에 박혀있는 숫자라면 마찬가지로 경우의 수가 더 줄어들 것이다. 그러니까 위의 경우가 최악의 경우에서 TwoPtrs() 의 포문이 도는 횟수를 구하는 방법이 된다.

그러면 단순히 경우의 수만을 생각해서 평균을 내면 TwoPtrs() 의 시간복잡도는 \(\Theta(50)\) 이 될 것이고, 이분탐색으로 인한 시간복잡도는 \(\log{200} \simeq 8\) 이 되어 합치면 투포인터 방법과 비슷한 평균 시간복잡도가 나오게 된다.

무엇이 더 빠른가?

백준 테스트 케이스 상에는 이 전략이 더 빨랐다.

3
100 100 100
100 100 199
0   199 100

위 같은 경우를 돌려보면 투포인터는 301 번 BFS() 를 돌리고 이분탐색은 698 번이나 돌려서 꽤나 차이가 나는데도 말이다.

이는 이분탐색이 빠른경우 10번 이내로 답을 찾을 수 있는 반면 투포인터는 무조건 200번 이상 탐색해야하기 때문에 생기는 차이로 보인다. 최악의 경우 투포인터가 3~4배 느리지만, 최선의 경우는 40배 이상 빠르기 때문이다.

이는 퀵소트를 연상시키지만, 퀵소트보다 더 좋은 조건에 있다. 최악의 경우라도 로그단위 차이라서 왠만한 범위에서는 속도가 극단적으로 차이가 나지 않으며, 최선의 경우에서는 몇십배 이상으로 빨라지기 때문이다.

평균적인 속도가 최악의 경우 시간복잡도와 비례한 문제들을 보다가 이런 문제를 보게되니 감회가 새롭다.

시간 복잡도

O(\(N^2 M\log{M}\))

• 여기서 \(M\) 은 Input 으로 들어오는 수의 범위로 200 이 된다.

코드

int n, max_v = -1, min_v = 1e9;
int board[101][101];
bool visitTB[101][101];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
inline bool Valid(int x, int y) { return x >= 0 && y >= 0 && x < n && y < n; }

bool BFS(int l, int r)
{
	if (board[0][0] > r || board[0][0] < l) return false;
	
	fill(visitTB[0], visitTB[n], 0);
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		for (int i = 0; i < 4; i++)
		{
			int x = cur.first + dx[i];
			int y = cur.second + dy[i];
			if (Valid(x, y) && board[y][x] <= r && board[y][x] >= l && !visitTB[y][x])
			{
				visitTB[y][x] = true;
				q.push({ x, y });
			}
		}
	}
	return visitTB[n-1][n-1];
}

bool TwoPtrs(int dist)
{
	int ans = 1e9;
	int begin = max(min_v,        max(board[0][0], board[n-1][n-1]) - dist);
	int end   = min(max_v - dist, min(board[0][0], board[n-1][n-1]));
	// for(int i = 0; i <= 200; i++) // 이러면 안됨
	for (int i = begin; i <= end; i++)
		if (BFS(i, i + dist)) return true;
	return false;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];
			max_v = max(max_v, board[i][j]);
			min_v = min(min_v, board[i][j]);
		}

	int ans = 1e9;
	// int begin = 0, end = 200; 이러면 안됨
	int begin = abs(board[0][0] - board[n-1][n-1]), end = max_v - min_v;
	while (begin <= end)
	{
		int m = (begin + end) / 2;
		if (TwoPtrs(m)) {
			ans = min(ans, m);
			end = m - 1;
		}
		else begin = m + 1;
	}

	cout << ans;
}