백준 스터디 14주차 - 발표

Q1. 9205 맥주 마시면서 걸어가기 > 문제 링크

50미터를 가려면 맥주 한 병을 마셔야 하고, 맥주는 20병을 넘을 수 없다. -> 편의점에 한 번 가면 편의점과 1000m 이내에 있는 좌표들로 이동할 수 있다.

그러므로 출발점, 편의점, 도착점의 좌표를 입력받고 모든 좌표들을 비교하여 1000 이내에 있으면 갈 수 있다는 뜻이므로 그래프를 서로 연결시켜준다.

이후 출발점에서부터 그래프 탐색을 시행하여, 도착점의 방문 여부를 파악해서, 방문했으면 그래프가 연결되어 있다는 의미이고, 그것은 즉 갈 수 있는 경로가 있는 것이므로 happy를 출력하고, 방문하지 못했으면 경로가 없는 것이므로 sad를 출력하면 된다.

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> street;
vector<int> graph[102];
int visit[102];

int distance(pair<int, int> p1, pair<int, int> p2){
	return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}


void dfs(int now) {
	visit[now] = true;
	for (int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i];
		if (visit[next] == false)
			dfs(next);
	}
}

int main() {
	int tc;
	cin >> tc;

	while (tc--) {

		street.clear();
		for (int j = 0; j < 102; j++) {
			graph[j].clear();
		}
		memset(visit,false, sizeof(visit));
		
		
		int con;
		cin >> con;

		for (int i = 0; i < con + 2; i++) {
			int x, y;
			cin >> x >> y;
			street.push_back(make_pair(x, y));
		}

		for (int j = 0; j < con + 2; j++) {
			for (int k = j + 1; k < con + 2; k++) {
				if (distance(street[j], street[k]) <= 1000) {
					graph[j].push_back(k);
					graph[k].push_back(j);
				}
			}
		}

		dfs(0);


		if (visit[con + 1]) cout << "happy" << endl;
		else cout << "sad" << endl;
	}

}

이 때 좌표값은 pair로 만들어 벡터에 저장하고, 출발점은 pair벡터에 가장 먼저 들어가있으므로 인덱스 값이 0이기 때문에 dfs는 0부터 시행한다.

---

Q2. 1890 점프 > 문제 링크

문제에서 '0' 지점으로 이동할 수 있는 세 가지 경우의 수를 보여주는 그림이다.

시작점은 무조건 거쳐야하므로 dp[0][0]은 1로 초기화 하고, (0,0)의 좌표값이 2이므로 그림에서 파란색으로 칠한 부분으로 이동할 수 있을 것이다. 그러면 해당 부분으로 오는 데 걸리는 경로의 수는 이전 지점까지의 경로의 수를 더해주면 된다.

#include <iostream>
using namespace std;

int n;
int g[101][101] = { 0, };
long long dp[101][101] = { 0, };

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> g[i][j];
		}
	}

	dp[0][0] = 1;

	for (int x = 0; x < n; x++) {
		for (int y = 0; y < n; y++) {
			int jump = g[x][y];

			if (y + jump < n && y != n-1) dp[x][y + jump] += dp[x][y];  // 왼쪽 이동
			if (x + jump < n && x != n-1) dp[x+jump][y] += dp[x][y]; // 아래쪽 이동
		}
	}
	
	cout << dp[n - 1][n - 1];

}

모든 점에서 탐색을 하되 시간을 줄이기 위해서 dp값이 0인 좌표에 대해서는 if문을 돌리지 않고 지나쳤다.
먼저 점프할 거리를 구해두고, 점프 이후의 좌표가 모서리를 넘지 않고, 현재 좌표가 모서리 좌표가 아닌 경우에 점프를 수행한다.
이때 점프된 좌표까지 가는 경로의 수는, 현재 좌표까지 오는 데 가능한 경로의 수를 더해주면 된다.
이런식으로 모든 경로를 계산한 후, 마지막 좌표의 dp값(경로의 수)를 출력해주면 된다.