[2146] 다리 만들기 - C++

2146번: 다리 만들기

1. 문제 요약

대륙간의 놓을 수 있는 다리 중 가장 짧은 다리의 길이를 알아내야 함

 

---

2. 전략

BFS를 써야 하는 것은 너무도 당연하다.

 

내가 생각한 방법은 정말 간단하다, 바다옆에 육지가 있는 부분에서 모두 BFS를 돌려 보는 것이다.

그런데 위의 방법에는 한 가지 문제가 있다.

 

내가 출발한 대륙에서 BFS를 돌려 다른 대륙에 도착한 건지, 아니면 빙 돌아와 내가 서 있었던 대륙에 다시 도착한 건지 알 방법이 없다. 

 

이 문제를 해결하기 위해서 나는 각 대륙마다 고유의 번호를 부여하는 방법을 선택하였다.

 

---

3. 주의 점

BFS를 두 번 사용한다

1. 섬에 번호를 적을 때
2. 짧은 다리를 찾을 때

 

---

4. 의사 코드

int  main(){
	int N;
    cin >> N;
	input(); //입력
	for(0~N){
    	for(0~N){
        	if(보드를 순회하다 육지(대륙)를 만난다면)
            	그 대륙에 번호를 배기는 BFS를 돌림(번호는 2부터 시작)
           	if(현재 위치(x, y)가 육지이고 && 주변에 물(0)이 하나라도 있다면)
            	대륙간의 가장 짧은 다리를 찾는 BFS를 돌림	
        }
    }
    답 출력
}

 

---

5. 코드

전체 코드

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int N, board[102][102], vis[102][102], isLandCnt = 1, ans = 2'000'000'000;
int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
queue<pair<int, int>> isLandQ;

// Out of Bounds Check(배열을 나가는지 체크하는 함수)
bool OOB(int x, int y){
  return x < 0 || x >= N || y < 0 || y >= N;
}

// 다리를 찾는 BFS함수
int findBridge(int localIsland){
  while(!isLandQ.empty()){
    int x, y; tie(x, y) = isLandQ.front(); isLandQ.pop();
    for(short dir = 0; dir < 4; ++dir){
      int nx = x + dx[dir], ny = y + dy[dir];
      if(OOB(nx, ny)) continue;
      if(vis[nx][ny] >= 0 || board[nx][ny] == localIsland) continue;
      if(board[nx][ny] > 0){
        return vis[x][y];
      }
      isLandQ.push({nx, ny});
      vis[nx][ny] = vis[x][y] + 1;
    }
  }
  return 2'000'000'000;
}

// 주변에 물이 하나라도 있는지 확인하는 함수
bool findZero(int x, int y){
  for(int dir = 0; dir < 4; ++dir){
    int nx = x+dx[dir], ny = y+dy[dir];
    if(OOB(nx, ny))continue;
    if(board[nx][ny] == 0) return true;
  }
  return false;
}

// 대륙에 고유의 번호를 부여하는 함수
void numberOfIsland(){
  while(!isLandQ.empty()){
    int x, y;
    tie(x, y) = isLandQ.front(); isLandQ.pop();
    for(int dir = 0; dir < 4; ++dir){
      int nx = x + dx[dir], ny = y + dy[dir];
      if(OOB(nx, ny) || board[nx][ny] != 1) continue;
      isLandQ.push({nx, ny});
      board[nx][ny] = isLandCnt;
    }
  }
}

int main(){
  init();
  memset(vis, -1, sizeof(vis));
  cin >> N;
  for(int i =0; i < N; ++i)
    for(int j = 0; j < N; ++j)
      cin >> board[i][j];

  for(int i = 0; i < N; ++i){
    for(int j = 0; j < N; ++j){
      if(board[i][j] == 1){
        ++isLandCnt;
        isLandQ.push({i, j});
        board[i][j] = isLandCnt;
        numberOfIsland();
      }
      if(board[i][j] > 1 && findZero(i, j)){
        isLandQ.push({i,j});
        vis[i][j] = 0;
        ans = min(ans, findBridge(board[i][j]));
        memset(vis, -1, sizeof(vis));
        isLandQ = queue<pair<int, int>>();
      }
    }
  }
  cout << ans;
  return 0;
}

 

다리를 찾는 함수

// 다리를 찾는 BFS함수
int findBridge(int localIsland){
  while(!isLandQ.empty()){
    int x, y; tie(x, y) = isLandQ.front(); isLandQ.pop();
    for(short dir = 0; dir < 4; ++dir){
      int nx = x + dx[dir], ny = y + dy[dir];
      if(OOB(nx, ny)) continue;
      if(vis[nx][ny] >= 0 || board[nx][ny] == localIsland) continue;
      if(board[nx][ny] > 0){
        return vis[x][y];
      }
      isLandQ.push({nx, ny});
      vis[nx][ny] = vis[x][y] + 1;
    }
  }
  return 2'000'000'000;
}

인자로 들어오는 localIsland는 내가 출발한 대륙을 알아보기 위해 받아오는 것

 

---

6. 새로 알게 된 것

memset

배열을 -1이나 0으로 초기화할 때 memset을 많이 사용하곤 한다.

int vis[102][102]

위와 같은 배열이 있다면 어떻게 초기화해야 할까

1. memset(vis, -1, 102*102)
2. memset(vis, -1, sizeof(vis))
3. memset(vis, -1, sizeof(int) * 102 * 102)

답: ②, ③ 

 

크기가 바이트 단위인걸 생각 못하고 ①번 방법으로 하면서 왜 계속 틀리는 거지? 했다.

 

init queue

큐를 초기화하는 방법

queue<pair<int, int>> Q

//초기화
Q = queue<pair<int,int>>();

이런 방법도 있었다.