16948 - 데스나이트

www.acmicpc.net/problem/16948

16948번: 데스 나이트

queue 컨테이너를 사용하면 c에서 배열을 잡아서 사용하는 것보다 저장공간을 덜 사용해 풀 수 있을 것이라고 생각함.

=> queue와 pair, vector를 사용하는 문제로 보임

 

1. 최단거리 구하기와 qeueu의 연관성

queue를 사용해야하는 이유 : 한 지점에서 갈 수 있는 모든 지점을 가고 갈 수 있는 모든 지점을 가기 위한 가중치가 모두 같음, 한 지점에서 여러번 이동하고 그 이동한 좌표를 모두 다 넣어줘야함.(한 지점에서 이동한 곳이 만약 n곳이라면 n곳을 가기 위해 필요한 가중치는 모두 같기에 이동한 곳을 모두 같이 생각해줘야함)

 

2. pair를 사용할 때 현재 좌표를 저장할 front pair를 설정해주고 sceond pair는 시작점에서 그 지점으로 가기 위해 이동한 횟수를 넣어줌. 

---

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
	vector <vector <bool> >  check(201, vector<bool>(201, false));

	int n;
	cin >> n;
	n = n - 1;
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	typedef pair <int, int> ci;
	
	queue<pair<ci, int> > q;

	int cnt = 0;
	q.push(make_pair(ci(a,b),cnt));
	check[a][b] = true;
	
	while(1)
	{

		if (q.front().first.first +2 <= n && q.front().first.second - 1>=0 && check[q.front().first.first + 2][q.front().first.second - 1] == false)
		{
			int x = q.front().first.first + 2;
			int y = q.front().first.second - 1;
			int t = q.front().second;
			q.push(make_pair(ci(x, y), t + 1));
			check[x][y] = true;
			
		}
		if (q.front().first.first + 2 <= n && q.front().first.second +1 <=n && check[q.front().first.first + 2][q.front().first.second + 1]==false)
		{
			int x= q.front().first.first + 2;
			int y =q.front().first.second + 1;
			int t = q.front().second;
			q.push(make_pair(ci(x, y), t + 1));
			check[x][y] = true;
			
		}
		if (q.front().first.second + 2 <= n && check[q.front().first.first][q.front().first.second + 2]==false)
		{
			int x = q.front().first.first;
			int y = q.front().first.second + 2;
			int t = q.front().second;
			q.push(make_pair(ci(x, y), t + 1));
			check[x][y] = true;
			
		}
		if (q.front().first.second -2 >= 0&& check[q.front().first.first][q.front().first.second - 2] == false)
		{
			int x = q.front().first.first;
			int y = q.front().first.second - 2;
			int t = q.front().second;
			q.push(make_pair(ci(x, y), t + 1));
			check[x][y] = true;
			
		}
		if (q.front().first.first - 2 >=0 && q.front().first.second - 1 >=0 && check[q.front().first.first - 2][q.front().first.second - 1]==false)
		{
			int x = q.front().first.first - 2;
			int y = q.front().first.second - 1;
			int t = q.front().second;
			q.push(make_pair(ci(x, y), t + 1));
			check[x][y] = true;
			
		}
		if (q.front().first.first - 2 >=0 && q.front().first.second + 1 <= n && check[q.front().first.first - 2][q.front().first.second + 1] == false)
		{
			int x = q.front().first.first - 2;
			int y = q.front().first.second + 1;
			int t = q.front().second;
			q.push(make_pair(ci(x, y), t + 1));
			check[x][y] = true;
			
		}

		else
		{
			q.pop();
			if (q.empty())
			{
				break;
			}
		}
		
		
		if (q.front().first.first == c && q.front().first.second == d)
		{
			cout << q.front().second << "\n";
			return 0;
		}
		
	}

	cout << "-1";
	

}

코드를 너무 길게 작성해서 가독성을 위해 줄여줄 필요가 있어보이기는 하지만, pair와 2차원 vector의 사용법을 익히기 위해 풀어봤음으로 넘어간다.

c로 풀었을 때, 배열 크기 때문에 문제가 됐는데 queue 컨테이너를 pair과 함께 사용하며 필요한만큼만 할당해서 문제없이 잘 작동하였다.

 

---

*tip

오류가 났던 부분

1. 무한루프를 돌았는데 check를 안 해줘서 갔던 좌표를 계속해서 반복하며 범위 내에서 왔다갔다 거리는 중이였음

=> check벡터 필수

2. -1을 출력하는 부분에서

while(!q.empty())라고 해서 -1을 출력하려고 했는데 계속 오류가 뜸.

생각해보니, 가장 뒤에서 무조건 frist와 second값을 숫자와 비교중인데 아예 q에 들은게 없다면 문제가 발생함 => 그 위에서 empty처리를 해줘야했음