문제 이해하기
두 개의 숫자 r, c와 n × m 크기의 격자(grid)가 주어집니다. 격자의 일부 셀은 검정색(B)이고, 나머지는 흰색(W)입니다. 한 번의 연산에서는 검정색 셀을 하나 선택한 뒤, 다음 두 가지 동작 중 정확히 하나를 수행할 수 있습니다.
- 선택한 셀이 속한 행 전체를 검정색으로 칠하기
- 선택한 셀이 속한 열 전체를 검정색으로 칠하기
목표는 r행 c열 위치의 셀을 검정색으로 만드는 데 필요한 최소 연산 횟수를 구하는 것이며, 불가능한 경우에는 -1을 반환해야 합니다.
예시
다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
| W | B | W | W | W |
| B | B | B | W | B |
| W | W | B | B | B |
r = 0, c = 3일 때 출력은 1입니다. 첫 번째 행 전체를 검정색으로 칠하면 아래와 같이 되기 때문입니다.
| B | B | B | B | B |
| B | B | B | W | B |
| W | W | B | B | B |
풀이 접근 방법
이 문제의 핵심은 이미 검정색인 셀을 기준으로 필요한 연산 횟수를 계산하는 것입니다. 검정색 셀 (i, j)가 있을 때, 이 셀을 활용해 목표 지점 (r, c)를 검정색으로 만드는 데 필요한 연산 횟수는 다음과 같이 정리할 수 있습니다.
- i == r이고 j == c인 경우: 목표 셀이 이미 검정색이므로 0번
- i == r 또는 j == c 중 하나만 만족하는 경우: 해당 행(또는 열)을 한 번만 칠하면 되므로 1번
- i != r이고 j != c인 경우: 행을 먼저 칠해 (i, c)를 검정색으로 만든 뒤 열을 칠하거나, 열을 먼저 칠해 (r, j)를 검정색으로 만든 뒤 행을 칠하면 되므로 2번
따라서 모든 검정색 셀에 대해 (i != r) + (j != c) 값을 계산한 뒤 그중 최솟값을 구하면 됩니다. 만약 검정색 셀이 하나도 없어 최솟값이 2보다 크다면 목표를 달성할 수 없으므로 -1을 반환합니다.
단계별 풀이 과정
이 문제를 해결하기 위해 다음 단계를 따릅니다.
n := grid의 행 개수
m := grid의 열 개수
ans := 무한대
i := 0부터 i < n까지 1씩 증가하며 반복:
j := 0부터 j < m까지 1씩 증가하며 반복:
matrix[i, j]가 'B'와 같으면:
ans := ans와 ((i와 r이 다르면 1, 같으면 0) + (j와 c가 다르면 1, 같으면 0)) 중 최솟값
ans > 2이면:
-1 반환
그렇지 않으면:
ans 반환C++ 구현 예시
더 나은 이해를 돕기 위해 다음 구현 예시를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<char>> matrix, int r, int c) {
int n = matrix.size();
int m = matrix[0].size();
int ans = 999999;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (matrix[i][j] == 'B') {
ans = min(ans, (i != r) + (j != c));
}
}
}
if (ans > 2) {
return -1;
}
else
return ans;
}
int main() {
vector<vector<char>> matrix = { { 'W', 'B', 'W', 'W', 'W' }, { 'B', 'B', 'B', 'W', 'B' }, { 'W', 'W', 'B', 'B', 'B' } };
int r = 0, c = 3;
cout << solve(matrix, r, c) << endl;
}입력
{ { 'W', 'B', 'W', 'W', 'W' }, { 'B', 'B', 'B', 'W', 'B' }, { 'W', 'W', 'B', 'B', 'B' } }, 0, 3출력
1