[Algorithm] 백준 2146번 다리 만들기

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

 

문제 풀이

초기에는 특정 섬에서 다른 섬까지 이동하는 경로를 dfs로 구현했음.

하지만 굉장히 바보같이 무식한 생각이라는 걸 뒤늦게 깨달은 후 좌표만으로 계산하여 문제를 해결함.

 

문제를 보면 최단거리를 찾는 문제로 착각하기 쉬운데, 이러한 트릭을 잘 해결하는 머리를 가지도록 해보자.

 

#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdio.h>
using namespace std;
int N;
int mapOrigin[101][101];
int map[101][101];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int answer;
 
struct Point {
    int x;
    int y;
    Point() : x(0), y(0) {};
    Point(int x, int y) :x(x), y(y) {};
};
 
vector<vector<Point>> result;
vector<Point> temp;
 
void changeMap(int x, int y, int val) {
    temp.push_back(Point(x, y));
    int cx, cy;
    for (int i = 0; i < 4; i++) {
        cx = dx[i] + x;
        cy = dy[i] + y;
        if (cx >= 0 && cy >= 0 && cx < N && cy < N) {
            if (map[cx][cy] == 0 && mapOrigin[cx][cy] == 1) {
                map[cx][cy] = val;
                changeMap(cx, cy, val);
            }
        }
    }
}
 
void comapreMin(vector<Point> t1, vector<Point> t2) {
    for (int i = 0; i < t1.size(); i++) {
        for (int j = 0; j < t2.size(); j++) {
            int temp = abs(t1[i].x - t2[j].x) + abs(t1[i].y - t2[j].y);
            if (answer > temp) {
                answer = temp;
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
    answer = 2 * N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &mapOrigin[i][j]);
        }
    }
    int val = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (mapOrigin[i][j] == 1 && map[i][j] == 0) {
                map[i][j] = val;
                temp = vector<Point>();
                changeMap(i, j, val);
                val++;
                result.push_back(temp);
            }
        }
    }
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result.size(); j++) {
            if (i == j) continue;
            comapreMin(result[i], result[j]);
        }
    }
    printf("%d", answer - 1);
    return 0;
}