백준_다리 만들기

https://www.acmicpc.net/problem/2146

[ 나의 문제 풀이 ]

1. 각 섬에 번호 부여 : 이중for문으로 map돌면서 섬 만날 때마다 BFS하면, 각 섬에 번호가 부여됨.

2. 거리 측정 후보 선택 : BFS돌면서, 바다와 인접해 있는 지역 좌표를 candidate라는 vector에 저장.

3. 거리 측정 : candidate에 있는 좌표들 끼리 거리측정함. 단, 당연히 다른 섬번호끼리만 좌표를 측정. 거리측정은 ABS(y2-y1) + ABS(x2-x1)으로 구하면 됨. 이 때, 거리 측정할 섬들 사이에, 다른 섬이 있을지 모름. 하지만 괜찮음. 생각해보면, 이 경우는 어차피 최단거리가 될리가 없기 때문임.

[ 나의 코드 ]

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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

#include <iostream> #include <queue> #include <vector>   #define MAX 102   using namespace std;   int N; int Map[MAX][MAX]; int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; vector<pair<int, int>> candidate;   void InData(){     int data;       cin >> N;       for (int Y = 1; Y <= N; Y++){         for (int X = 1; X <= N; X++){             cin >> data;             if (data) Map[Y][X] = -1;         }     } }   void BFS(int Y, int X, int number){     queue<pair<int, int>> q;     q.push(make_pair(Y, X));     Map[Y][X] = number;       while (!q.empty()){         int curY = q.front().first;         int curX = q.front().second;         q.pop();           // BFS         for (int i = 0; i < 4; i++){             int nextY = curY + dir[i][1];             int nextX = curX + dir[i][0];             if (Map[nextY][nextX] == -1){                 q.push(make_pair(nextY, nextX));                 Map[nextY][nextX] = number;             }         }           // Candidate select         for (int i = 0; i < 4; i++) {             int nextY = curY + dir[i][1];             int nextX = curX + dir[i][0];               if (Map[nextY][nextX] == 0) {                 if (nextY == 0 || nextX == 0 || nextY == MAX || nextX == MAX)                     continue;                 candidate.push_back(make_pair(curY, curX));                 break;             }         }     } }   void Labeling(){     int number = 1;     for (int Y = 1; Y <= N; Y++){         for (int X = 1; X <= N; X++){             if (Map[Y][X] == -1)                 BFS(Y, X, number++);         }     } }   int ABS(int value) {     return (value < 0) ? -value : value; }   int main(){     int minDist = 999;       InData();       Labeling();           for (int i = 0; i < candidate.size(); i++)     {         int curX = candidate[i].second;         int curY = candidate[i].first;         for (int j = 0; j < candidate.size(); j++)         {             int nextX = candidate[j].second;             int nextY = candidate[j].first;             if (Map[curY][curX] == Map[nextY][nextX])                 continue;             int dist = ABS(nextY - curY) + ABS(nextX - curX) - 1;             if (dist < minDist)                 minDist = dist;         }     }     cout << minDist << endl; }