반응형
https://leetcode.com/problems/shortest-bridge/description/
Shortest Bridge - LeetCode
Can you solve this real interview question? Shortest Bridge - You are given an n x n binary matrix grid where 1 represents land and 0 represents water. An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly
leetcode.com
첫번째 섬과 인접한 물의 좌표와, 두번째 섬과 인접한 물의 좌표를 구해줍니다.
구해진 좌표를 이용하여 두 섬 사이의 최단 거리를 구해줍니다.
class Solution {
public:
int d[5] = {0,-1,0,1,0};
bool visit[100][100] = {false};
vector<pair<int, int>> first, second;
int shortestBridge(vector<vector<int>>& grid) {
for(int i=0; i<grid.size(); i++) {
for(int j=0; j<grid.size(); j++) {
if(grid[i][j]) {
dfs(grid, i, j, first.empty()? first : second);
}
}
}
int res = INT_MAX;
for(auto& f : first) {
for(auto& s : second) {
int dist = abs(f.first - s.first) + abs(f.second - s.second) + 1;
res = min(res, dist);
}
}
return res;
}
void dfs(vector<vector<int>>& grid, int x, int y, vector<pair<int, int>>& arr) {
if(!grid[x][y]) {
arr.push_back({x, y});
return;
}
if(visit[x][y]) return;
visit[x][y] = true;
for(int i=0; i<4; i++) {
int nx = x + d[i];
int ny = y + d[i + 1];
if(nx < 0 || ny < 0 || nx >= grid.size() || ny >= grid.size()) continue;
dfs(grid, nx, ny, arr);
}
}
};
첫번째 섬과 인접한 물의 좌표를 구해줍니다.
해당 좌표에서부터 두번째 섬을 찾을 때 까지 BFS를 수행해줍니다.
class Solution {
public:
int d[5] = {0,-1,0,1,0};
int visit[100][100] = {0};
queue<pair<int, int>> q;
int shortestBridge(vector<vector<int>>& grid) {
for(int i=0; i<grid.size(); i++) {
for(int j=0; j<grid.size(); j++) {
if(grid[i][j] && q.empty()) {
dfs(grid, i, j);
}
}
}
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if(grid[x][y]) return visit[x][y] - 1;
for(int i=0; i<4; i++) {
int nx = x + d[i];
int ny = y + d[i + 1];
if(nx < 0 || ny < 0 || nx >= grid.size() || ny >= grid.size()|| visit[nx][ny]) continue;
q.push({nx, ny});
visit[nx][ny] = visit[x][y] + 1;
}
}
return -1;
}
void dfs(vector<vector<int>>& grid, int x, int y) {
if(!grid[x][y]) {
q.push({x, y});
visit[x][y] = 1;
return;
}
if(visit[x][y]) return;
visit[x][y] = 1;
for(int i=0; i<4; i++) {
int nx = x + d[i];
int ny = y + d[i + 1];
if(nx < 0 || ny < 0 || nx >= grid.size() || ny >= grid.size()) continue;
dfs(grid, nx, ny);
}
}
};
반응형
'Algorithm' 카테고리의 다른 글
LeetCode 2542. Maximum Subsequence Score (0) | 2023.05.26 |
---|---|
LeetCode 347. Top K Frequent Elements (0) | 2023.05.22 |
LeetCode 399. Evaluate Division (0) | 2023.05.20 |
LeetCode 1557. Minimum Number of Vertices to Reach All Nodes (0) | 2023.05.18 |
LeetCode 2130. Maximum Twin Sum of a Linked List (0) | 2023.05.17 |