백준 2146번 C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int MAX = 101;
int n;
int map[MAX][MAX];
int visited[MAX][MAX];
struct Move {
	int x, y;
};
Move mv[4] = { {-1,0}, {1,0}, {0,1}, {0,-1} };

void dfs(int i, int j,int index) {
	map[i][j] = index;

	for (int k = 0; k < 4; k++) {
		int movei = i + mv[k].x;
		int movej = j + mv[k].y;

		if (movei >= 0 && movei < n && movej >= 0 && movej < n) {
			if (visited[movei][movej] == -1 && map[movei][movej] == 1) 
				dfs(movei, movej, index);
		}
	}
}

int bfs(int i, int j,int value, int count) {
	int minvalue = 987654321;
	queue<pair<pair<int,int>,pair<int, int>>> q;
	q.push(make_pair(make_pair(i, j),make_pair(value,count)));
	visited[i][j] = 1;

	while (!q.empty()) {
		int currenti = q.front().first.first;
		int currentj = q.front().first.second;
		int currentvalue = q.front().second.first;
		int currentcounts = q.front().second.second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int movei = currenti + mv[k].x;
			int movej = currentj + mv[k].y;

			if (movei >= 0 && movei < n && movej >= 0 && movej < n) {
				if (map[movei][movej] == 0) {
					if (visited[movei][movej] == -1) {
						q.push(make_pair(make_pair(movei, movej), make_pair(currentvalue, currentcounts + 1)));
						visited[movei][movej] = currentcounts + 1;
					}
					else if (visited[movei][movej] > currentcounts + 1) {
						q.push(make_pair(make_pair(movei, movej), make_pair(currentvalue, currentcounts + 1)));
						visited[movei][movej] = currentcounts + 1;
					}
				}
				if (map[movei][movej] != 0 && map[movei][movej] != currentvalue ) 
					minvalue = min(minvalue, currentcounts);
				if (map[movei][movej] == currentvalue && visited[movei][movej] == -1) {
					q.push(make_pair(make_pair(movei, movej), make_pair(currentvalue, 0)));
					visited[movei][movej] = 1;
				}
			}
		}
	}
	return minvalue;
}

int main(void) {
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	memset(visited, -1, sizeof(visited));
	int index = 2;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1) {
				dfs(i, j, index);
				index++;
			}
		}
	}
	memset(visited, -1, sizeof(visited));
	int answer = 987654321;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] >= 2 && visited[i][j] == -1) 
				answer = min(answer, bfs(i, j, map[i][j],0));
		}
	}
	cout << answer << endl;
	return 0;
}