카카오 코드페스티벌 예선2

문제 보기

간단하게 요약해보면 m*n개의 교차점을 갖는 격자를 도로 지도라고 생각하고, 가장 왼쪽 위 지점에서 가장 오른쪽 아래 지점으로 가는 최단 경로의 수를 구하는 문제이다. 단, city_map[m][n] 이라는 2차원 벡터에 0, 1, 2 셋 중 하나의 값이 저장되어 있는 데, 이는 [i][j] 교차로에 주어지는 어떤 제약 사항을 나타낸다. 0이면 아무 제약이 없고, 1이면 좌, 우회전이 불가능한 교차로, 2이면 통행이 불가능한 교차로이다.

잘못된 풀이

int solution(int m, int n, vector<vector<int> > city_map) {
	vector<vector<int> > routes;
	vector<int> element(n, 0);
	for (int i = 0; i < m; i++)
		routes.push_back(element);

	routes[0][0] = 1;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (city_map[i][j] == 1)
			{
				routes[i][j] = 0;
				continue;
			}


			if (i > 0 && city_map[i - 1][j] == 0)
				routes[i][j] += routes[i - 1][j];
			else if (i > 1 && city_map[i - 1][j] == 2)
				routes[i][j] += routes[i - 2][j];

			if (j > 0 && city_map[i][j - 1] == 0)
				routes[i][j] += routes[i][j - 1];
			else if (j > 1 && city_map[i][j - 1] == 2)
				routes[i][j] += routes[i][j - 2];

			cout << routes[i][j] << " ";
		}
		cout << endl;
	}

	return routes[m - 1][n - 1];
}

처음에 생각해서 짰던 코드이다. 예전에 중학교? 정도 수학 시간에 격자에서 최단 경로의 수 구하기 할 때, 격자 교차점마다 거기까지 갈 수 있는 경로의 수를 위쪽의 숫자 + 왼쪽의 숫자로 구했던 것에서 착안하였다.
routes는 격자점마다 거기까지 가는 경로 수를 저장하는 2차원 벡터이다. 가장 왼쪽 위의 출발점은 1의 값을 갖고, 2중 반복문을 거치면서 바로 왼쪽과 위쪽의 city_map을 검사하여 제한사항(회전금지, 통행금지)가 없으면 그대로 왼쪽, 위쪽의 수를 더해주고, 회전이 금지되어 있으면 2칸 왼쪽 또는 2칸 위쪽의 경로 수만큼을 더해주었다.
회전 금지가 걸려 있으면 해당 지점까지 가는 경로의 수가 의미가 없을 것 같다. 왜냐하면, 어차피 다음 지점까지 경로의 수를 셀 때 위, 왼쪽에 회전금지가 걸려 있으면 그거보다 한칸 더 왼쪽, 위쪽의 값을 참조하기 때문이다. 때문에 이 부분은 신경쓰지 않기로 했다. 그런데 문제는, 이 코드가 회전 금지가 연속되어 있는 경우에 이 신경 안쓴 값을 참조하게 되어 있다는 것이다. 예를 들어, 2, 1 , 2, 2 에 회전 금지가 걸려 있는 경우, 2, 3 까지의 경로의 수를 구할 때 2, 2 에 회전금지가 걸려 있으므로 2, 1 까지의 경로 수를 더해주게 되는데, 이는 1, 1 에서 오는 경로 수까지 더해진 값이다. 1, 1 에서 오는 경로는 2, 1 에 회전 금지가 걸려 있으므로 실제로는 불가능한 경로이다.
이 문제를 해결하기 위해 여러 방면으로 생각해 보았으나… 기존 의 routes 변수를 쓰는 방법으로는 답이 없는 듯 했다. 카카오 테크 블로그의 해설 힌트 를 참조해 보니, 위쪽에서 오는 경로의 수와 왼쪽에서 오는 경로의 수를 분리하여 저장하는 방법을 사용하고 있었다.

다시 풀어보기

 int solution(int m, int n, vector<vector<int> > city_map) {
	vector<vector<int> > routesV;
	vector<int> elementV(n + 1, 0);
	for (int i = 0; i < m + 1; i++)
		routesV.push_back(elementV);

	vector<vector<int> > routesH;
	vector<int> elementH(n + 1, 0);
	for (int i = 0; i < m + 1; i++)
		routesH.push_back(elementH);

	routesH[1][0] = 1;
	for (int i = 1; i < m + 1; i++)
	{
		for (int j = 1; j < n + 1; j++)
		{
			if (city_map[i-1][j-1] == 1)
				continue;

			else if (city_map[i-1][j-1] == 0)
			{
				routesV[i][j] = routesV[i - 1][j] + routesH[i][j - 1];
				routesH[i][j] = routesV[i][j];
			}

			else if (city_map[i-1][j-1] == 2)
			{
				routesV[i][j] = routesV[i - 1][j];
				routesH[i][j] = routesH[i][j - 1];
			}
		}
	}

	return routesH[m][n];
}

routesV는 해당 지점에서 아래로 갈 수 있는 경로 수, routesH는 해당 지점에서 우측으로 갈 수 있는 경로 수이다. 이렇게 경로의 방향으로 변수를 분리함으로서 해당 지점의 city_map에 어떤 제약사항이 있냐에 따라에만 케이스를 분리하여 훨씬 간단한 로직을 갖게 되었다. 앞의 풀이와 달리 왼쪽, 위쪽 교차로의 제약 사안을 파악하지 않고 해당 지점만 관찰하므로, 왼쪽과 위쪽의 삼거리에서는 맵 바깥의 경로수를 참조하는 오류를 일으키는 문제가 있어 왼쪽과 위쪽에 1줄 여유를 두고 경로 수를 0으로 초기화하였다. 따라서, 1, 1 지점에서 m, n 까지 배열 번호를 사용하게 되며, routesH[0][1] = 1 로 두어 이중 for문의 첫 바퀴를 돌 때 routesV[1][1] = routesH[1][1] = 1로 만들도록 하였다.

풀이의 원본은 github 에서도 보실 수 있습니다.