[백준] 2194-유닛 이동시키기(C++)

문제링크:https://www.acmicpc.net/problem/2194

2194번: 유닛 이동시키기

bfs를 사용하는 문제였습니다.

하지만 기존 탐색과는 다르게 탐색하는 유닛의 크기가 1X1이 아닌 값이기 때문에 

이동하면서 숫자 넘어가는 숫자들의 범위나 이동할 수 있는지 여부를 반복문을 통해서 판별해야하기 때문에 구현문제로 분류하였습니다.

 

 

• 값 입력
• 상하좌우로 움직기
• 이동할때 모든 값이 배열을 벗어나는지 장애물이 있는지 확인하기
• 이동가능할 경우 visited에 표시하기
• 값 출력

 

정답코드입니다.

#include <iostream>
#include <queue>
using namespace std;
int arr[501][501] = { 0 };
int visited[501][501] = { 0 };
int n = 0, m = 0, a = 0, b = 0, k = 0;
int start_y, start_x, destination_y, destination_x;

int x_ar[4] = { 0,0,1,-1 };
int y_ar[4] = { 1,-1,0,0 };

void bfs() {
	queue<int> que[2];
	que[0].push(start_y);
	que[1].push(start_x);
	visited[start_y][start_x] = 1;
	while (!que[0].empty()) {
		int yy = que[0].front();
		int xx = que[1].front();
		que[0].pop(), que[1].pop();

		
		for (int k = 0; k < 4; k++) {
			bool jud = true;
			for (int i = 0; i < a; i++) {
				for (int j = 0; j < b; j++) {
					int y = i + yy + y_ar[k];
					int x = j + xx + x_ar[k];
					if (y >= 1 && y <= n&&x >= 1 && x <= m) {
						if (arr[y][x] == 1) {
							jud = false;
							break;
						}
					}
					else { //해당공간에서 벗어나니까 
						jud = false;
						break;
					}
				}
				if (jud == false)
					break;
			}
			if (jud == true && visited [yy+y_ar[k]][xx+x_ar[k]] == 0) {
				visited[yy + y_ar[k]][xx + x_ar[k]] = visited[yy][xx] + 1;
				que[0].push(yy + y_ar[k]);
				que[1].push(xx + x_ar[k]);
			}
		}
		
	}
}

int main() {
	cin >> n >> m >> a >> b >> k;
	int num_a = 0, num_b = 0;
	for (int i = 0; i < k; i++) {
		cin >> num_a >> num_b;
		arr[num_a][num_b] = 1;
	}
	cin >> start_y >> start_x >> destination_y >> destination_x;

	bfs();

	cout << visited[destination_y][destination_x] - 1 << '\n';
}