[S3] 백준 26169번 세 번 이내에 사과를 먹자 C++ 너비 우선 탐색, 비트마스킹

리뷰

 

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

백트래킹 문제이긴 한데.. BFS로 풀려고 시도했다, 결과는 성공

 

 

전역 변수

• sx, sy : 시작 위치를 저장할 변수
• lst : 맵 정보를 저장할 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 위치 x, y, 먹은 사과의 개수 c, 소요 시간 t, 방문 정보 b를 정의할 구조체

 

함수

1. bfs

int bfs()

 

너비 우선 탐색을 통해 3턴 이내로 사과 2개를 먹을 수 있는지 여부를 체크하기 위한 함수

1. Pos타입의 큐 q를 초기화 하고, 시작 위치 sx, sy, 먹은 사과 0, 소요 시간 0, 방문 정보 2^nx * 5 + ny를 push한다.
2. q가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
3. 첫 번째 기저 조건으로 먹은 사과의 개수 cc가 2라면 1을 리턴해 준다.
4. 두 번째 기저 조건으로 소요 시간 ct가 3이라면 continue처리해 준다.
5. 4방향 탐색을 시작하고, 맵의 범위 내에 있으며 장애물이 아니고, 방문하지 않은 지역이라면 이동을 진행한다.
6. 이동한 지역에 사과가 있다면 먹은 사과 nc를 1만큼 증가시켜 준다.
7. q에 이동 위치nx, ny, 새로운 먹은 사과 nc, 새로운 소요 시간 nt, 새로운 방문 정보를 push해준다.
8. 만약 q에 요소가 없어 while루프가 종료된 경우 0을 리턴해 준다.

 

문제풀이

1. 5 * 5크기의 맵 정보를 lst배열에 입력 받아준다.
2. 시작 위치 sx, sy를 입력 받아주고, bfs함수를 호출하여 받은 리턴값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 이동했던 위치는 장애물이 있는 칸으로 변경된다는 조건이 있다.
• 따라서 비트마스킹을 통해 방문 정보를 업데이트하면 다른 케이스와 독립적으로 시뮬레이션을 돌릴 수 있다.

 

정답 코드

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

int sx, sy;
int lst[5][5];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int x, y, c, t, b;
};

int bfs() {
	queue<Pos> q;
	q.push({ sx, sy, 0, 0, (int)pow(2, sx * 5 + sy) });

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, cc = pos.c, ct = pos.t, cb = pos.b;
		if (cc == 2) return 1;
		if (ct == 3) continue;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nc = cc, nt = ct + 1;
			if (0 <= nx && nx < 5 && 0 <= ny && ny < 5 && lst[nx][ny] != -1 && !(cb & (int)pow(2, nx * 5 + ny))) {
				if (lst[nx][ny]) nc++;
				q.push({ nx, ny, nc, nt, cb + (int)pow(2, nx * 5 + ny)});
			}
		}
	}
	return 0;
}

int main() {
	for (int i = 0; i < 5; ++i)
		for (int j = 0; j < 5; ++j)
			cin >> lst[i][j];

	cin >> sx >> sy;
	cout << bfs();
}