mojo's Blog
[백준 25189] 시니컬한 개구리 본문
문제 링크 : 25189번: 시니컬한 개구리 (acmicpc.net)
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;
}
'백준 > BFS, DFS' 카테고리의 다른 글
[백준 1939] 중량제한 (0) | 2022.01.24 |
---|---|
[백준 2842] 집배원 한상덕 (0) | 2022.01.21 |
[백준 17142] 연구소 3 (0) | 2022.01.08 |
[백준 2573] 빙산 (0) | 2021.11.14 |
[백준 15684] 사다리 조작 (0) | 2021.09.05 |