[BAE/<JOON> 문제풀이] 1577. 도로의 개수

https://www.acmicpc.net/problem/1577

1577번: 도로의 개수

핵심:: 

도로를 잘 구분 짓는게 중요함

 

풀이::

이 문제를 틀리는 이유는 공사중인 도로를 식별하는 방법을 잘못 정하는 오류를 범했을 확률이 높다.

 

직접 다 하나씩 해봐서 틀려봤으므로 하나씩 나열해보겠다.

 

1. 배열에 공사도로 시작점과 끝점을 표시하고 공사중인 지점일 경우 경우의 수 0으로 처리

 -> 가장 간단한 오류다. 한 점마다 4개의 도로가 있는데 공사중이지 않은 나머지 3개의 도로도 지나갈 수 없는 도로로 취급한다.

 

2. 1번 방법으로 처리하지만 (i - 1, j) , (i, j - 1) 두 개의 지점이 모두 공사중인 경우에만 0으로 처리

 -> 두개의 도로가 나란히 공사중일 경우 세로로는 통행이 가능해야하지만 세로 지점들도 공사중인 것으로 계산한다.

 

결국 모든 공사중인 도로의 좌표를 배열로 가지고 있으며 검색해보는 O(N^3) 풀이로 해결했다. 

 

시간과 입력의 크기를 보면 그냥 처음부터 N^3으루 구현하는건데 괜히 예쁘게 구현하겠다고 시간만 날렸다.

 

의견::

꿀문제 

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ull = long long;

struct r {
	int x1, y1, x2, y2;
};

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<ull>> dp(n + 2, vector<ull>(m + 2, 0));
	int w;
	cin >> w;	
	vector<r> road(w + 1);
	for (int i = 1; i <= w; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;		
		road[i].x1 = x1 < x2 ? x1 + 1: x2 + 1;
		road[i].x2 = x1 > x2 ? x1 + 1 : x2 + 1;
		road[i].y1 = y1 < y2 ? y1 + 1 : y2 + 1;
		road[i].y2 = y1 > y2 ? y1 + 1 : y2 + 1;
	}

	dp[1][1] = 1;
	for (int i = 1; i <= n + 1; i++) {
		for (int j = 1; j <= m + 1; j++) {
			if (i == 1 && j == 1) continue;
			ull s1 = dp[i - 1][j];
			ull s2 = dp[i][j - 1];
			for (int k = 1; k <= w; k++) {
				if (road[k].x2 == i && road[k].y2 == j) {
					if (road[k].x1 == i - 1 && road[k].y1 == j) {
						s1 = 0;
					}
					if (road[k].x1 == i && road[k].y1 == j - 1) {
						s2 = 0;
					}
				}

				if (s1 == 0 && s2 == 0) break;
			}
			
			dp[i][j] = s1 + s2;
		}
	}

	/*for (int i = 1; i <= n + 1; i++) {
		for (int j = 1; j <= m + 1; j++) {
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}*/

	cout << dp[n + 1][m + 1] << "\n";

	return 0;
}