130. Surrounded Regions - medium
문제
Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
제한사항
입출력 예
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Example:
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'.
Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'.
Two cells are connected if they are adjacent cells connected horizontally or vertically.
풀이
- DFS, BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
void BFS(vector<vector<char>>& board, pair<int, int>&& index){
int n = board.size();
int m = board[0].size();
queue<pair<int, int>> q;
q.push(index);
while(!q.empty()){
auto i = q.front();
q.pop();
// '*'이면 이미 조회했으므로 건너뜀
if(board[i.first][i.second] == '*')
continue;
// 현재 위치를 조회하지 않았다면, 현재값에서 주변을 탐색
else if(board[i.first][i.second] == 'O
// 현재 값을 ''*'로 바꿈으로써 조회했다는 것을 표시
board[i.first][i.second] = '*';
// 현재 위치에서 상하좌우를 탐색 하는데,
// 값이 'O'인 것만 탐색
if(0 <= i.first - 1 && board[i.first-1][i.second] == 'O')
q.push({i.first - 1, i.second});
if(i.first + 1 < n && board[i.first+1][i.second] == 'O')
q.push({i.first + 1, i.second});
if(0 <= i.second - 1 && board[i.first][i.second-1] == 'O')
q.push({i.first, i.second - 1});
if(i.second + 1 < m && board[i.first][i.second+1] == 'O')
q.push({i.first, i.second + 1});
}
}
}
void solve(vector<vector<char>>& board) {
if(board.empty())
return;
int n = board.size();
int m = board[0].size();
// 첫번쨰 행의 BFS
for(auto i = 0 ; i < m ; ++i)
BFS(board, {0, i});
// 마지막 행의 BFS
for(auto i = 0 ; i < m ; ++i)
BFS(board, {n-1, i});
// 첫번쨰 열의 BFS
for(auto i = 1 ; i < n - 1 ; ++i)
BFS(board, {i, 0});
// 마지막 열의 BFS
for(auto i = 1 ; i < n - 1 ; ++i)
BFS(board, {i, m-1});
// 탐색한것을 기반으로 값을 변환
for(auto& row : board){
for(auto& val : row){
if(val == '*')
val = 'O';
else if(val == 'O')
val = 'X';
}
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
type Index struct {
first, second int
}
// 재귀로 구현한 BFS
func BFS(board [][]byte, i Index){
n := len(board)
m := len(board[0])
if board[i.first][i.second] == '*' {
return
} else if board[i.first][i.second] == 'O' {
// 현재 값을 ''*'로 바꿈으로써 조회했다는 것을 표시
board[i.first][i.second] = '*';
// 현재 위치에서 상하좌우를 탐색 하는데,
// 값이 'O'인 것만 탐색
if 0 <= i.first - 1 && board[i.first-1][i.second] == 'O' {
index := Index{i.first - 1, i.second}
BFS(board, index);
}
if i.first + 1 < n && board[i.first+1][i.second] == 'O' {
index := Index{i.first + 1, i.second}
BFS(board, index);
}
if 0 <= i.second - 1 && board[i.first][i.second-1] == 'O' {
index := Index{i.first, i.second - 1}
BFS(board, index);
}
if i.second + 1 < m && board[i.first][i.second+1] == 'O' {
index := Index{i.first, i.second + 1}
BFS(board, index);
}
}
}
func solve(board [][]byte) {
if len(board) == 0 {
return
}
n := len(board)
m := len(board[0])
// 첫번쨰 행의 BFS
for i := 0 ; i < m ; i += 1{
index := Index{0, i}
BFS(board, index);
}
// 마지막 행의 BFS
for i := 0 ; i < m ; i += 1{
index := Index{n-1, i}
BFS(board, index);
}
// 첫번쨰 열의 BFS
for i := 1 ; i < n - 1 ; i += 1{
index := Index{i, 0}
BFS(board, index);
}
// 마지막 열의 BFS
for i := 1 ; i < n - 1 ; i += 1{
index := Index{i, m-1}
BFS(board, index);
}
// 탐색한것을 기반으로 값을 변환
for i, row := range board {
for j := range row {
if board[i][j] == '*' {
board[i][j] = 'O';
} else if board[i][j] == 'O' {
board[i][j] = 'X';
}
}
}
}