[C++] 백준/BOJ - 17836 : 공주님을 구해라

---

문제 이해 단계

 

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

맵 크기 N M이 주어지고, 주어진 시간 T 안에 벽을 피해 오른쪽 아래에 도달해야 한다.

최단 거리를 구하는 문제인데 특이한 점은
그람이라는 검이 있는 곳에 도달하면 벽을 뚫고 지나갈 수 있다는 점이다.

즉, 그람을 획득한 순간 어디든 자유롭게 다닐 수 있다는 뜻이다.

이 조건이 있을 때, 왼쪽 위에서 오른쪽 아래까지 도달하는데
걸리는 최단 시간을 구하는 문제이다.

 

 

---

문제 접근 단계

최단 거리를 탐색하는 대표적인 2차원 BFS문제이다.

조금 특이한 점은 그람이라는 검의 존재이다.
그람을 획득하는 순간 벽의 유무는 상관 없어진다.

즉, 그람을 획득하는 순간부터는 벽이 없다고 가정하고 BFS를 진행해도 된다는 뜻이다.

위 문제는 최단 경로를 찾는 것이기 때문에
두 가지 경로 중 더 짧은 경로를 채택하면 된다.

 

---

1. 바로 공주가 있는 곳으로 향하는 방식

이 방식은 그람의 획득 유무는 중요하지 않다.

이 방식을 따져보는 이유는 그람을 획득하지 않아도 더 빠를 수도 있기 때문이다.

 

---

2. 그람을 획득하고 공주가 있는 곳으로 향하는 방식

이 방식은 그람이 있는 위치를 최단거리로 이동한 뒤,
그 위치에서 공주의 위치로 최단거리로 이동한다.

최종적으로 1과 2 방식을 비교한 후, 더 짧은 이동시간을 가진 방식이 답이 된다.

 

 

---

문제 구현 단계

void Bfs(int s1, int s2) {
	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++) c[i][j] = 0;

	queue<pair<int, int>> q;
	q.push(make_pair(s1, s2));
	c[s1][s2] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > N || ny < 1 || 
				ny > M || map[nx][ny] == 1) continue;
			if (!c[nx][ny]) {
				c[nx][ny] = c[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
}

해당 좌표에서 시작하는 BFS함수이다.

최단거리를 구하는 함수인데, BFS를 여러 번 돌려야 하기 때문에
visit을 뜻하는 c [][]를 false로 초기화한다.

인자로 받는 s1, s2는 x, y좌표를 뜻하며,
x, y에서 출발하는 최단 거리를 뜻한다.

int Gram(int s1, int s2) {
	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++) c[i][j] = 0;

	queue<pair<int, int>> q;
	q.push(make_pair(s1, s2));
	c[s1][s2] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > N || ny < 1 || ny > M) continue;
			if (!c[nx][ny]) {
				c[nx][ny] = c[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
	if (c[N][M] > 0) return c[N][M] - 1;
	else return 0;
}

Gram을 획득한 뒤, 해당 좌표에서 BFS를 실행하는 함수이다.

위 함수는 벽의 유무와는 상관없이 BFS가 돌아간다.
이 점 외에는 일반적인 BFS와 똑같다.

공주 위치의 값이 0 이상이면, 출력하고 아니면 0을 반환한다.

cin >> N >> M >> T;
	pair<int, int> gram;
	for(int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) gram = make_pair(i, j);
		}

	Bfs(1, 1);
	int v1 = 10001;
	int v2 = 10001;
	int getSword = 10001;
	if (c[N][M] > 0) v1 = c[N][M] - 1;
	if (c[gram.first][gram.second] > 0) getSword = c[gram.first][gram.second] - 1;
	if(Gram(gram.first, gram.second)) v2 = getSword + Gram(gram.first, gram.second);

	int answer = min(v1, v2);

	if (answer > T || answer < 0) cout << "Fail";
	else cout << answer;

실질적인 main 함수 부분이다.
변수로는 v1, v2, getsword 세 가지를 둔다.

v1는 공주에게 바로 가는 방식
v2는 그람으로 가는 경로 + 그람에서 공주로 가는 경로
getsword는 그람으로 가는 경로를 뜻한다.

v1과 v2 중 더 작은 값을 answer에 저장해 두고,
그 answer가 T보다 크거나 0보다 작을 경우 Fail을 출력한다.

마지막으로 전체코드를 쓰고 풀이를 끝내겠다.

#include <iostream>
#include <queue>

using namespace std;

int map[101][101];
int c[101][101];
int N, M, T;
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };

void Bfs(int s1, int s2) {
	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++) c[i][j] = 0;

	queue<pair<int, int>> q;
	q.push(make_pair(s1, s2));
	c[s1][s2] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > N || ny < 1 || 
				ny > M || map[nx][ny] == 1) continue;
			if (!c[nx][ny]) {
				c[nx][ny] = c[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
}
int Gram(int s1, int s2) {
	for (int i = 1; i <= 100; i++)
		for (int j = 1; j <= 100; j++) c[i][j] = 0;

	queue<pair<int, int>> q;
	q.push(make_pair(s1, s2));
	c[s1][s2] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > N || ny < 1 || ny > M) continue;
			if (!c[nx][ny]) {
				c[nx][ny] = c[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
	if (c[N][M] > 0) return c[N][M] - 1;
	else return 0;

}
int main() {
	cin >> N >> M >> T;
	pair<int, int> gram;
	for(int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) gram = make_pair(i, j);
		}

	Bfs(1, 1);
	int v1 = 10001;
	int v2 = 10001;
	int getSword = 10001;
	if (c[N][M] > 0) v1 = c[N][M] - 1;
	if (c[gram.first][gram.second] > 0) getSword = c[gram.first][gram.second] - 1;
	if(Gram(gram.first, gram.second)) v2 = getSword + Gram(gram.first, gram.second);

	int answer = min(v1, v2);

	if (answer > T || answer < 0) cout << "Fail";
	else cout << answer;
	return 0;
}

 

 

---

시행착오

이 문제는 보자마자 풀이가 떠올랐던 전형적인 BFS문제에
작은 응용만 하면 되는 문제였기 때문에 그렇게 힘들게 풀진 않았다.

BFS의 원리만 잘 이해하고 있다면 어렵지 않게 풀 수 있는 문제였다.