[백준 25189] 시니컬한 개구리

문제 링크 : 25189번: 시니컬한 개구리 (acmicpc.net)

25189번: 시니컬한 개구리

---

 

2022 서강대학교 청정수컵 Round G번 문제이다.

문제 유형은 전형적인 BFS 로 보이지만, 인풋 사이즈로 인해 난이도가 급상승한 느낌이다.

N, M 값의 최대값이 100 이였다면 navie 하게 \(O(N^{3})\) 으로 해결이 가능했을 것이다.

그러나, N, M 값의 최댓값이 1000 이므로 navie 한 접근이 불가능하므로 약간의 생각이 필요했다.

 

우선 문제에서 특별하게 봐야할 것은 다음과 같다.

최대 한 번 개구리밥을 무시하고 점프하기로 했다.
개구리밥을 무시하고 점프할 때는 상하좌우 중 한 방향으로 서식지 내에서 원하는 칸만큼 점프할 수 있다.

 

특정 지점에 위치한 개구리는 상하좌우 중 한 방향으로 원하는 만큼 이동이 가능하다는 것이다.

따라서, 3차원 방문 배열(visited[1001][1001][2])을 통해 개구리가 최대 한 번은 개구리밥을 무시하고

점프할 수 있도록 지정할 수 있도록 하였다.

3차원 방문 배열에 대한 자세한 설명은 다음과 같다.

 

• visited[row][col][0] : 개구리가 개구리밥을 무시하지 않고 (row, col) 에 방문했는지 true/false 를 통해 확인
• visited[row][col][1] : 개구리가 최대 한 번 개구리밥을 무시하고 (row, col) 에 방문했는지 true/false 를 통해 확인 

개구리가 최대 한 번 개구리밥을 무시할 경우에 해당 위치를 (row, col) 이라고 해보자.

그렇다면 해당 row 에서 개구리밥을 무시했는지, 해당 col 에서 개구리밥을 무시했는지를 판단하기 위한

배열이 추가로 필요한데 이를 1차원 방문 배열(visited_row[1001], visited_col[1001])을 선언하여 해결했다.

1차원 방문 배열에 대한 자세한 설명은 다음과 같다.

 

• visited_row[row] : 해당 row 에서 개구리가 개구리밥을 무시한 경우 true 마킹, 아닐 경우 false 마킹 
• visited_col[col] : 해당 col 에서 개구리가 개구리밥을 무시한 경우 true 마킹, 아닐 경우 false 마킹

BFS 의 성질을 이용해 가장 먼저 특정 (row, col) 에 도착할 경우 개구리밥을 무시할 수 있도록 해줘야 한다.

다음과 같은 경우를 생각해보도록 하자.

 

 

위와 같이 이동이 가능이 하며 시작 지점인 (1, 1) 에서 두 가지 케이스를 통해 개구리밥을 무시하지 않고

4번째 행까지 이동한다고 해보자.

 

• case 1 : (1, 1) => (2, 1) => (3, 1) => (4, 1)
• case 2 : (1, 1) => (1, 2) => (2, 2) => (4, 2)

위와 같은 case 를 통해 아래와 같이 개구리가 배치되었다고 해보자.

 

 

이때, (4, 1) 으로 이동한 개구리가 개구리밥을 무시하고 원하는 만큼 점프를 한다고 가정해보자.

즉, row = 4 일 때 모든 col 으로 이동이 가능하도록 할 수 있으며 이때 visited_row[4] 를 true 로 마킹한다. 

row = 4 로 고정하고 모든 col 으로 이동할 때 개구리는 다음과 같이 배치가 된다.

 

 

그 후에 (4, 2) 에 위치하고 있는 개구리에 대해서 이 개구리 또한 개구리밥을 무시하고 

원하는 만큼 점프를 할 수 있도록 하는 operation 을 해줘야 할까?

이미 visited_row[4] 를 true 로 마킹하였기 때문에 해당 row 는 이미 어떤 개구리가 먼저 도착하여

개구리밥을 무시한 채로 모든 col 으로 이동을 하는 operation 을 했다는 것을 알 수 있다.

따라서 나중에 도착한 개구리에 대해서는 이러한 operation 을 하지 않도록 하며 개구리밥을 먹으면서

점프를 하도록 해야 한다.

 

따라서, visited_row, visited_col 배열을 통해 어떠한 개구리가 미리 해당 row, col 에 도착할 경우

개구리밥을 무시한 채로 row, col 을 고정한 채로 원하는 col, row 만큼 이동을 시키고 나중에 도착한

개구리는 이미 도착한 개구리가 개구리밥을 무시한 채로 이동했기 때문에 개구리밥을 먹으면서 

이동해야 하는 것을 알 수 있다.

 

시간 복잡도는 worst case 일 경우 모든 좌표에 방문하는데 NM 이며,

특정 row, col 에서 원하는 만큼 이동하는데 NM 이므로 총 2NM 으로  O( 2NM ) = O( NM ) 이다.

 

풀이 코드

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M;
int r_f, c_f, r_h, c_h;
int a[1001][1001];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
bool visited[1001][1001][2];
bool visited_row[1001], visited_col[1001];

typedef struct info {
	int x;
	int y;
	int jump_cnt;
	int op;
} Info;

bool in_area(int x, int y) {
	return x >= 1 && x <= N && y >= 1 && y <= M;
}

void input() {
	cin >> N >> M;
	cin >> r_f >> c_f >> r_h >> c_h;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> a[i][j];
		}
	}
}

void solution() {
	queue<Info> Q;
	Info info, next_info;

	visited[r_f][c_f][0] = true;
	Q.push({ r_f, c_f, 0, 0 });
	while (!Q.empty()) {
		info = Q.front();
		Q.pop();

		if (info.x == r_h && info.y == c_h) {
			cout << info.jump_cnt;
			return;
		}
		if (info.op == 0) {
			next_info.op = 1;
			next_info.jump_cnt = info.jump_cnt + 1;
			if (!visited_row[info.x]) {
				visited_row[info.x] = true;
				next_info.x = info.x;
				for (int y = 1; y <= M; y++) {
					next_info.y = y;
					if (!visited[next_info.x][next_info.y][next_info.op]) {
						visited[next_info.x][next_info.y][next_info.op] = true;
						Q.push(next_info);
					}
				}
			}
			if (!visited_col[info.y]) {
				visited_col[info.y] = true;
				next_info.y = info.y;
				for (int x = 1; x <= N; x++) {
					next_info.x = x;
					if (!visited[next_info.x][next_info.y][next_info.op]) {
						visited[next_info.x][next_info.y][next_info.op] = true;
						Q.push(next_info);
					}
				}
			}
		}
		next_info.op = info.op;
		next_info.jump_cnt = info.jump_cnt + 1;
		for (int i = 0; i < 4; i++) {
			next_info.x = info.x + a[info.x][info.y] * dx[i];
			next_info.y = info.y + a[info.x][info.y] * dy[i];
			if (in_area(next_info.x, next_info.y)
				&& !visited[next_info.x][next_info.y][next_info.op]) {
				visited[next_info.x][next_info.y][next_info.op] = true;
				Q.push(next_info);
			}
		}
	}
	cout << -1;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solution();

	return 0;
}