BOJ
[C++] 백준 33926번 - 인덕이와 보드게임
민규링
2025. 6. 13. 12:14
문제 접근
문제 내용을 요약하면 다음과 같다.
N * M 격자판 모양 보드의 각 칸에 정수값이 존재하고, 또한 각 칸은 흰색 또는 검은색으로 칠해져 있다.
1행 1열에 공이 소환되며, 1행 1열의 정수값이 공에 기록된다.
공이 다른 칸으로 이동하면 해당 칸에 적혀 있는 정수가 공에 더해지며, 만약 이동을 마친 칸이 검은색이라면 공에 적힌 수의 부호가 반전된다. (흰색은 반전되지 않는다.)
단, 이동할 때 대각선 방향은 허용하지 않으며 한 번에 변으로 인접한 다른 한 칸으로만 이동할 수 있다.
이 때, 1행 1열에서 N 행 M 열까지 공을 최단 경로로 이동시켰을 때 공에 기록된 수의 최댓값을 구한다.
최단 경로라는 문구만 보고 BFS 기반으로 코드를 작성하다 이상함을 느꼈다.
격자판에 특정 칸을 밟지 못한다는 등의 제약 조건이 존재하지 않는다면, 1행 1열에서 N 행 M 열까지 이동하는 최단 경로는 N 행 만큼 아래쪽으로 이동하고 M 행 만큼 오른쪽으로 이동하여 N 행 M 열에 도달하는 모든 경로가 해당되기 때문이다.
따라서 굳이 BFS를 쓸 필요가 없이, 해당 문제에서 말하는 최단 경로들은 모두 오른쪽 아래 방향으로 이동하는 추세를 알 수 있음.
어느 자연수 x, y ( 1 ≤ x ≤ N, 1 ≤ y ≤ N )가 존재할 때, 1행 1열에서 x 행 y 열까지 도달하는 최단 경로는 다음과 같다.
문제에서 원하는 해는 N 행 M 열에 최단 경로로 도달했을 때 공에 기록될 수 있는 수들 중 최댓값이다.
그렇다면, x 행 y 열까지 도달했을 때의 최댓값은 다음 점화식을 만족하는 값일 것이다.
Score = N * M size의 격자판.
Score[x][y] = 1행 1열에서 x 행 y 열까지 최단 경로로 도달했을 때 공에 적혀 있는 수의 최댓값.
Board = N * M size의 격자판.
Board[x][y] = x 행 y 열에 존재하는 정수값.
if x == 1 :
Score[x][y] = Score[x][y - 1] + Board[x][y]
else if y == 1 :
Score[x][y] = Score[x - 1][y] + Board[x][y]
else :
Score[x][y] = max(Score[x - 1][y], Score[x][y - 1]) + Board[x][y]
하지만 문제에서 조건이 하나 더 존재한다. 바로 이동 후 도달한 칸이 검은색이면 공에 적힌 수의 부호가 반전된다는 것이다.
도달한 칸이 검은 색일 때, 먼저 공에 적힌 수와 해당 칸의 정수를 합한 후 부호를 반전시키게 된다.
위 점화식 대로 검은색 칸에서의 최댓값을 계산하면 수가 반전되므로 최솟값이 되어버린다.
검은색 칸에서 최댓값을 도출해내려면, 최솟값을 구한 후 부호를 반전시켜야 한다.
결국 각 칸 까지 최단 경로로 도달했을 때의 최댓값만 기억하는 것이 아닌 최솟값 또한 기억해야 한다.
따라서 모든 조건을 고려했을 때, 각 칸이 가지는 최댓값 및 최솟값을 구하는 점화식은 다음과 같다.
Score = N * M size의 격자판. 각 칸은 {최솟값, 최댓값} 쌍으로 구성되어 있음.
Score[x][y] 의 최솟값 = 1행 1열에서 x 행 y 열까지 최단 경로로 도달했을 때 공에 적혀 있는 수의 최솟값.
Score[x][y] 의 최댓값 = 1행 1열에서 x 행 y 열까지 최단 경로로 도달했을 때 공에 적혀 있는 수의 최댓값.
Board = N * M size의 격자판.
Board[x][y] = x 행 y 열에 존재하는 정수값.
if Board[x][y]'s Color = White :
if x == 1 :
Score[x][y] 의 최솟값, 최댓값 = Score[x][y - 1] 의 최솟값( 혹은 최댓값 ) + Board[x][y] // 경로가 하나밖에 없기에 두 값이 같음.
else if y == 1 :
Score[x][y] 의 최솟값, 최댓값 = Score[x - 1][y] 의 최솟값 (혹은 최댓값 ) + Board[x][y] // 경로가 하나밖에 없기에 두 값이 같음.
else :
Score[x][y]의 최솟값 = min(Score[x - 1][y] 의 최솟값, Score[x][y - 1]) + Board[x][y]
Score[x][y]의 최댓값 = max(Score[x - 1][y] 의 최댓값, Score[x][y - 1]) + Board[x][y]
else : // Board[x][y]'s Color = Black
if x == 1 :
Score[x][y] 의 최솟값, 최댓값 = Score[x][y - 1] 의 최솟값( 혹은 최댓값 ) + Board[x][y] // 경로가 하나밖에 없기에 두 값이 같음.
else if y == 1 :
Score[x][y] 의 최솟값, 최댓값 = Score[x - 1][y] 의 최솟값 (혹은 최댓값 ) + Board[x][y] // 경로가 하나밖에 없기에 두 값이 같음.
else :
Score[x][y] 의 최솟값 = min( -1 * (Score[x - 1][y] 의 최댓값 + Board[x][y] ), -1 * (Score[x][y - 1] 의 최댓값+ Board[x][y]) )
Score[x][y] 의 최댓값 = max( -1 * (Score[x - 1][y] 의 최솟값 + Board[x][y]), -1 * (Score[x][y - 1] 의 최솟값 + Board[x][y]) )
해당 점화식으로 Score 격자판의 N 행 M 열에 존재하는 최솟값, 최댓값까지 구했다면, 해당 칸의 최댓값이 문제의 해가 된다.
입력 예제
2 5
2 -5 1 -3 5
3 -8 -3 5 8
0 1 0 0 0
1 1 0 1 1
출력 예제
7
전체 코드
// 33926
#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\n"
#define ll long long
using namespace std;
enum Color {White, Black};
vector<vector<int>> board;
vector<vector<Color>> color;
// {최솟값, 최댓값}
vector<vector<pair<ll, ll>>> score;
int N, M;
void solution() {
score[0][0] = { board[0][0], board[0][0] };
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
if (row == 0 && col == 0) continue;
if (row == 0) {
ll now_score;
now_score = score[row][col - 1].first + board[row][col];
if (color[row][col] == Black) now_score *= -1;
score[row][col] = make_pair(now_score, now_score);
}
else if (col == 0) {
ll now_score;
now_score = score[row - 1][col].first + board[row][col];
if (color[row][col] == Black) now_score *= -1;
score[row][col] = make_pair(now_score, now_score);
}
else {
if (color[row][col] == Black) {
score[row][col].first = min(-1 * (score[row - 1][col].second + board[row][col]), -1 * (score[row][col - 1].second + board[row][col]));
score[row][col].second = max(-1 * (score[row - 1][col].first + board[row][col]), -1 * (score[row][col - 1].first + board[row][col]));
}
else {
score[row][col].first = min(score[row - 1][col].first, score[row][col - 1].first) + + board[row][col];
score[row][col].second = max(score[row - 1][col].second, score[row][col - 1].second) + board[row][col];
}
}
}
}
//cout << "*******최댓값**********" << endl;
//for (auto row : score) {
// for (auto col : row) {
// cout << col.second << " ";
// }
// cout << endl;
//}
//cout << "*******최솟값**********" << endl;
//for (auto row : score) {
// for (auto col : row) {
// cout << col.first << " ";
// }
// cout << endl;
//}
cout << score[N - 1][M - 1].second;
}
int main(void) {
cin.tie(0); ios::sync_with_stdio(false);
cin >> N >> M;
board.resize(N, vector<int>(M));
color.resize(N, vector<Color>(M));
score.resize(N, vector<pair<ll, ll>>(M));
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
cin >> board[row][col];
}
}
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
int c;
cin >> c;
if (!c) color[row][col] = White;
else color[row][col] = Black;
}
}
solution();
}
풀이 후기
문제 제대로 안읽고 BFS로 풀었다가 시간 버렸다... 문제를 꼼꼼히 읽어야겠다.