[G5] 백준 16509번 장군 C++ BFS, 시뮬레이션

리뷰

 

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

상을 움직이는 문제지만, 이동 중 다른 기물이 있다면 이동할 수 없는 조건이 추가된 문제

 

 

전역 변수

• Pos : 말의 위치와 현재 까지 이동한 시간을 기록하기 위한 구조체
• King : 왕의 위치를 저장하기 위한 Pos타입 변수
• Elep : 상의 위치를 저장하기 위한 Pos타입 변수
• r, c : 맵의 행과 열의 제한을 두기 위한 정수형 상수 변수
• dx, dy : 상의 이동을 시뮬레이션 하기 위한 방향 배열, 각 케이스 마다 하드 코딩 해주었다.
• map : 왕의 위치를 1로 표기하여 좀 더 편하게 시뮬레이션 하기 위한 정수형 2차 배열
• v : 방문 처리를 기록하기 위한 정수형 2차 배열

 

함수

1. bfs

int bfs()

 

너비 우선 탐색을 통해 상이 왕에게 도달한 최소 시간을 구하기 위한 함수

1. Pos타입의 큐 q를 초기화 하고, 상의 초기 위치와 초기 시간 0을 추가해 준다.
2. 상의 초기위치에 방문처리를 해준 후 큐가 빌 때 까지 반복문을 수행한다.
3. 큐에서 요소 하나를 꺼내고 해당 위치를 cx, cy 시뮬레이션 시간을 ct로 초기화 해준다.
4. 기저조건으로 만약 map의 cx, cy 위치가 1이라면 ct를 리턴해 주면 된다.
5. 8방향 탐색을 하면서 상의 이동 경로를 시뮬레이션 돌려준다.
6. 이동 중 다른 기물을 만났다면 더 이상 탐색할 필요가 없다.
7. 도착지가 맵 범위 안이면서 경로상 다른 기물을 만나지 않았다면 방문처리 후 큐에 추가해 준다.
8. 만약 탐색이 종료될 때 까지 왕에게 도달하지 못했다면 -1을 리턴해 준다.

 

문제풀이

1. 상과 왕의 위치를 입력 받은 후 각각의 Pos타입 변수에 할당해 준다.
2. 시뮬레이션 편의를 위해 맵 상에서 왕의 위치를 1로 저장해 준다.
3. bfs 함수를 통해 시뮬레이션을 진행하고 리턴 값을 바로 출력해 준다.

 

참고 사항

경로 상 다른 기물이 있는지 확인 할 때 마지막에 도달한 위치는 왕이 되어도 된다.

위 조건을 추가하지 않을 경우 왕의 위치를 찾을 수 없다.

 

 

정답 코드

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

struct Pos {
	int x, y, t;
};

Pos King;
Pos Elep;

const int r = 10;
const int c = 9;

//int dx[] = { -3, -3, -2, 2, 3, 3, 2, -2 };
//int dy[] = { -2, 2, 3, 3, 2, -2, -3, -3 };

int dx[8][3] = {
	{-1, -1, -1},
	{-1, -1, -1},
	{0, -1, -1},
	{0, 1, 1},
	{1, 1, 1},
	{1, 1, 1},
	{0, 1, 1},
	{0, -1, -1}
};

int dy[8][3] = {
	{0, -1, -1},
	{0, 1, 1},
	{1, 1, 1},
	{1, 1, 1},
	{0, 1, 1},
	{0, -1, -1},
	{-1, -1, -1},
	{-1, -1, -1}
};

int map[r][c];
int v[r][c];

int bfs() {
	queue<Pos> q;
	q.push({ Elep.x, Elep.y, 0 });
	v[Elep.x][Elep.y] = 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t;
		if (map[cx][cy]) return ct;

		for (int i = 0; i < 8; ++i) {
			int nx = cx, ny = cy, nt = ct + 1, flag = 1;
			for (int j = 0; j < 3; ++j) {
				nx += dx[i][j], ny += dy[i][j];
				if (0 <= nx && nx < r && 0 <= ny && ny < c) {
					if (map[nx][ny] && j < 2) {
						flag = 0;
						break;
					}
				}
				else {
					flag = 0;
					break;
				}
			}
			if (flag) {
				v[nx][ny] = 1;
				q.push({ nx, ny, nt });
			}
		}
	}
	return -1;
}

int main() {
	cin >> Elep.x >> Elep.y >> King.x >> King.y;
	map[King.x][King.y] = 1;
	cout << bfs();
}