Junnnho

www.acmicpc.net/problem/1103

문제

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

입력

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

-------------------------------------------------------------------------------------------------------

오랜만에 백준을 풀면서 포스팅을 했습니다.

이번 문제는 난이도 골드1의 게임 문제를 풀어보겠습니다.

항상 그렇듯 문제를 풀기 전에 어떤 식으로 풀 것인지 접근하는 것이 중요하다고 생각합니다.

문제를 읽어보면 기본적으로 dfs, bfs 같은 탐색을 이용한다는 것을 유추할 수 있고,

N이 50정도면 최대한 이동할 수 있는 범위를 찾고자 할 때 매 구간 캐시값을 저장해두지 않으면 시간초과가 날 것이므로 캐시값을 저장해두는 다이나믹 프로그래밍 방식인 것을 유추할 수 있습니다.

dp의 차원을 정할 때는 어떤 정보가 필요할 것인지 고려해줘야 하는데,

현재 문제의 경우에는 단순히 dp[y][x] = 위치 y,x 에서 갈 수 있는 최대한의 이동거리 만을 알면 되기 때문에

3차원, 4차원까지 추가적인 배열을 사용할 필요가 없습니다.

이외에는 문제에서 요구하는대로 이동해주면서 가장 많이 이동할 수 있는 거리를 dp를 사용해서

문제를 해결해주시면 됩니다.

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
int N, M;
string arr[50];
ll dp[50][50];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,-1,1 };
bool INF = false;

ll dfs(int y, int x) {
	// 이동할 수 없는 경우 이동거리를 -1 만큼 반환해주어서 계산해준다
	if (y < 0 || y >= N || x < 0 || x >= M || arr[y][x] == 'H' || INF) return -1;

	ll& res = dp[y][x];
	// dp[y][x]가 -2 인 경우 이미 한번 방문한 곳이므로
	// 더 확인할 필요없이 무한루프가 된다
	if (res == -2) {
		INF = true;
		return 0;
	}
	// -1이 아닌 경우 dp값을 갖고 있는 것이므로 사용해주면 된다
	if (res != -1) return res;

	// 애초에 방문한 현재 위치를 -2와 같은 임의의 값으로 바꿔주어서
	// 이미 방문한 곳임을 표시해준다
	res = -2;
	ll ans = 0;

	int move = arr[y][x]-'0';

	for (int i = 0; i < 4 && !INF; i++) {
		int yy = y + (my[i]*move);
		int xx = x + (mx[i]*move);
		// 가장 많이 이동할 수 있는 거리를 찾는다
		ans = max(ans, dfs(yy, xx) + 1);
	}

	return res = ans;
}


int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	memset(dp, -1, sizeof(dp));
	dfs(0, 0);
	if (INF) cout << "-1";
	else cout << dp[0][0] + 1;
}

BOJ : https://www.acmicpc.net/problem/2194

스타크래프트와 같은 게임을 하다 보면 어떤 유닛을 목적지까지 이동시켜야 하는 경우가 종종 발생한다. 편의상 맵을 N×M 크기의 2차원 행렬로 생각하자. 또한 각각의 유닛은 크기를 가질 수 있는데, 이를 A×B 크기의 2차원 행렬로 생각하자. 아래는 5×5 크기의 맵과 2×2 크기의 유닛에 대한 한 예이다. S는 시작점을 나타내며 E는 끝점을 나타낸다.

유닛은 상하좌우의 네 방향으로만 움직일 수 있다. 단, 유닛의 일부분이 장애물이 설치된 부분(위의 예에서 색이 칠해진 부분)을 지날 경우, 위의 예에서는 시작 위치에서 위로 이동하는 경우는 허용되지 않는다.

위의 예는 유닛을 오른쪽으로 세 칸, 위쪽으로 세 칸 움직이면 목적지에 도달할 수 있고, 이 경우가 가장 적은 이동 회수를 거치는 경우이다. 이동하는 도중에 유닛이 맵 밖으로 나가는 경우는 허용되지 않는다.

맵의 정보와 유닛의 정보가 주어졌을 때, 유닛을 목적지까지 움직이기 위해 필요한 최소의 이동 회수를 구하는 프로그램을 작성하시오.

백준 2194번 유닛 이동시키기 문제입니다.

구현부류에 해당하고 간단한 BFS 문제였습니다.

시작지점의 유닛 좌측상단의 좌표를 기준으로 하기 때문에

BFS 탐색간에 유닛의 크기만큼 전체가 장애물을 피해서 이동이 가능한지 판단해주시면서 탐색해주시면 됩니다.

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

queue<pair<pii, int> > q;

int n, m, a, b, k, dx, dy;
bool visit[502][502];
bool arr[502][502];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };

bool test(int y, int x) {

	for (int i = 0; i < a; i++)
		for (int j = 0; j < b; j++)
			if (arr[y + i][x + j]) return false;

	return true;
}


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m >> a >> b >> k;

	for (int i = 0; i < k; i++) {
		cin >> dy >> dx;
		arr[dy][dx] = true;
	}

	int sy, sx, ey, ex;
	cin >> sy >> sx >> ey >> ex;
	q.push({ {sy,sx},0 });
	int answer = -1;

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (y == ey && x == ex) {
			answer = cnt;
			break;
		}

		for (int i = 0; i < 4; i++) {
			int yy = y + my[i];
			int xx = x + mx[i];
			if (yy > 0 && yy + a - 1 <= n && xx > 0&& xx + b - 1 <= m && !visit[yy][xx] && test(yy, xx)) {
				visit[yy][xx] = true;
				q.push({ {yy,xx},cnt + 1 });
			}
		}
	}

	cout << answer;

	return 0;
}

BOJ : https://www.acmicpc.net/problem/14750

과제로 이 문제를 풀게 되어서 간단하게 방법만 소개하고자 한다

알아야할 정보는 다음과 같다

1. N K H M 순으로 인풋이 주어진다

2. N개만큼 다각형의 좌표가 주어진다(반시계방향)

3. H개만큼 홀의 갯수가 주어진다

4. M개만큼 쥐의 마리수가 주어진다

5. 각 홀은 최대 K마리의 쥐가 숨을 수 있다

6. 각 쥐는 당장 시야에 보이는 홀에만 들어갈 수 있다

   조건으로는 쥐와 홀에 대해서 선을 그엇을때 다른 벽이나 모서리와 겹치지 않아야한다.

7. 각 쥐는 반드시 다각형 내부에 존재한다 -> 다각형 선분위에 존재하지 않는다

8. 각 홀은 반드시 벽(선분)에 존재한다

9. 두개이상의 홀이나 쥐가 같은 위치에 존재하지 않는다

이때 모든 쥐가 숨을 수 있나 없나를 묻는 문제로,

문제를 해결하기 위해 필요한 지식은 

선분 교차확인법, 이분매칭 이렇게 2가지이다.

쥐와 홀의 쌍에 대해서 모든 벽과 선분교차를 확인하여

쥐가 들어갈 수 있는 홀을 따로 찾아둔 후에,

이분매칭을 통해서 쥐가 최대로 숨을 수 있는 마리수를 찾는다.

이때 이분매칭의 값이 쥐의 마리수와 같다면 possible이 된다

BOJ : https://www.acmicpc.net/problem/1647

마을을 최소의 가중치를 가지는 간선으로 연결한 후에

다시 2개의 집합으로 나누어야 한다

문제의 조건에서 마을에는 최소 1개의 집만 있으면 된다고 하였으므로

어떤 간선이든 잘라도 이 조건이 유지된다

그러므로 MST로 연결된 모든 간선 중에서 가장 큰 가중치를 갖는 간선을 삭제해주면 답이된다