2-4. 숲속의 기사 ★★★★☆

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Pos
{
	int x;
	int y;
	Pos(int x, int y)
	{
		this -> x = x;
		this -> y = y;
	}
};

int dis[2][1001][1001];

int main()
{
	int w, h, res = 2147000000;
	
	cin >> w >> h;
	
	int dx[4] = {1, 0, -1, 0};
	int dy[4] = {0, 1, 0, -1};
	
	queue<Pos> Q1;
	queue<Pos> Q2;
	
	vector<vector<int>> Map(h, vector<int>(w, 0));
	
	for(int i = 0; i < h; i++)
	{
		for(int j = 0; j < w; j++)
		{
			cin >> Map[i][j];
			if(Map[i][j] == 2)
			{
				Q1.push(Pos(i, j));
				dis[0][i][j] = 1;
			}
			
			if(Map[i][j] == 3)
			{
				Q2.push(Pos(i, j));
				dis[1][i][j] = 1;
			}
		}
	}
	
	while(!Q1.empty())
	{
		Pos temp = Q1.front();
		Q1.pop();
		
		int x = temp.x;
		int y = temp.y;
		
		for(int i = 0; i < 4; i++)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];
			
			if(xx < 0 || xx >= h || yy < 0 || yy >= w) continue;
			
			if(dis[0][xx][yy] == 0 && Map[xx][yy] != 1)
			{
				dis[0][xx][yy] = dis[0][x][y] + 1;
				Q1.push(Pos(xx, yy));	
			}	
		}	
	}
	
	while(!Q2.empty())
	{
		Pos temp = Q2.front();
		Q2.pop();
		
		int x = temp.x;
		int y = temp.y;
		
		for(int i = 0; i < 4; i++)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];
			
			if(xx < 0 || xx >= h || yy < 0 || yy >= w) continue;
			
			if(dis[1][xx][yy] == 0 && Map[xx][yy] != 1)
			{
				dis[1][xx][yy] = dis[1][x][y] + 1;
				Q2.push(Pos(xx, yy));	
			}	
		}	
	}
	
	for(int i = 0; i < h; i++)
	{
		for(int j = 0; j < w; j++)
		{
			if(Map[i][j] == 4)
			{
				if(dis[0][i][j] != 0 && dis[1][i][j] != 0)
				{
					int minDis = dis[0][i][j] + dis[1][i][j] - 2;
					if(minDis < res) res = minDis;
				}
			}
		}
	}
	
	cout << res << "\n";
	return 0;
	
}

1. dis[0][1001][1001] = 영희가 갈 수 있는 모든 영역까지의 거리

2. dis[1][1001][1001] = 기사가 갈 수 있는 모든 영역까지의 거리

3. 3차원 배열로 BFS를 활용해서 각 거리를 모두 계산한다. 단, 영희와 기사가 있던 자리를 다시 가면 안 되기 때문에 그 자리를 1로 한다.

4. 다음 for문으로 사과 하나의 좌표를 꺼내서 사과-영희, 사과-기사 거리를 구한다.

(영희 - 사과, 사과 - 기사) 이렇게 두 거리는 결국 (영희 - 사과 - 기사) 까지의 거리와 같다.

따라서 dis[0]와 dis[1]을 확인해서 두 값을 더하고, -2를 한다. -2를 하는 이유는 영희와 기사가 있던 자리를 다시 가지 않게 하기위해 그 자리를 각각 1로 했기 때문에 -(1*2)를 해주는 것이다.