[P5] 백준 17267번 상남자 C++ 너비 우선 탐색

리뷰

 

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

상태 관리가 필요한 0-1BFS문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n, m : 맵의 세로/가로 크기를 저장할 변수
• l, r : 왼쪽, 오른쪽 이동 가능 횟수를 저장할 변수
• Pos : 현재 위치와 남은 왼쪽, 오른쪽 이동 가능 횟수를 정의할 구조체
• dx, dy : 4방향 탐색을 위한 방향 배열
• d : 현재 위치에서 왼쪽으로 갈 수 있는 횟수를 저장할 2차원 배열

 

함수

1. bfs

int bfs(int sx, int sy) {
	queue<Pos> q;
	q.push({ sx, sy, l, r });
	d[sx][sy] = l;
	int cnt = 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.cx, cy = pos.cy, cll = pos.ll, clr = pos.lr;

		for (int i = 0; i < 4; ++i) {
			if (i == 2 && !clr) continue;
			if (i == 3 && !cll) continue;
			int nx = cx + dx[i], ny = cy + dy[i], nlr = i == 2 ? clr - 1 : clr, nll = i == 3 ? cll - 1 : cll;

			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (d[nx][ny] >= nll) continue;
				if (d[nx][ny] == -1) ++cnt;
				d[nx][ny] = nll;
				q.push({ nx, ny, nll, nlr });
			}
		}
	}
	return cnt;
}

 

시작 위치에서부터 갈 수 있는 모든 위치를 방문하고, 갈 수 있는 위치의 개수를 반환하는 함수

 

 

문제풀이

1. n, m, l, r값을 입력 받고, 변수 sx, sy를 초기화한다.
2. memset함수를 통해 d배열의 값을 -1로 초기화한다.
3. n*m크기의 맵 정보를 입력 받아 1일 경우 d의 값을 1001로, 2일 경우 sx, sy에 위치 정보를 저장한다.
4. bfs함수에 sx, sy를 매개변수로 전달하여 호출한다.
5. bfs함수 내부에서 변수 sx, sy에 매개변수를 파싱하여 저장한다.
6. Pos타입의 큐 q를 초기화 하고, sx, sy, l, r을 push한다.
7. d[sx][sy]를 l로 초기화 하고, 변수 cnt를 1로 저장한다.
8. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 뽑아 변수 cx, cy, cll, clr에 파싱한다.
9. 4방향을 탐색하며, 오른쪽 방향인데 clr이 0이거나 왼쪽 방향인데 cll이 0일 경우 continue처리한다.
10. 변수 nx, ny, nlr, nll에 이동할 위치와 이동 후 남은 방향 횟수를 저장한다.
11. 이동할 위치가 맵의 범위 안에 있다면 이동을 수행한다.
12. 이동한 위치의 d값이 nll이상이라면 continue처리한다.
13. 이동한 위치가 미방문 상태라면 cnt를 증가시킨다.
14. d[nx][ny]를 nll로 저장하고, nx, ny, nll, nlr을 q에 push한다.
15. 모든 탐색을 마친 후 cnt를 반환한다.

 

트러블 슈팅

1. 논리형 배열을 사용해 방문 여부로만 상태를 체크했다가 WA를 받아 정수형 배열로 변경하였다.
2. 현재 위치에서 왼쪽으로 갈 수 있는 최선의 경우를 탐색해주는 것으로 로직을 변경하여 AC를 받았다.

 

참고 사항

1. 오른쪽으로 이동 후엔 왼쪽으로 다시금 이동할 수 없게 설계하였다.
2. 왼쪽으로 이동 시 남은 이동 횟수를 비교하여 늦게 방문하더라도 방문 처리가 가능하도록 설계하였다.

 

정답 코드

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

const int N = 1000;
int n, m;
int l, r;
struct Pos {
	int cx, cy, ll, lr;
};
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int d[N][N];

int bfs(int sx, int sy) {
	queue<Pos> q;
	q.push({ sx, sy, l, r });
	d[sx][sy] = l;
	int cnt = 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.cx, cy = pos.cy, cll = pos.ll, clr = pos.lr;

		for (int i = 0; i < 4; ++i) {
			if (i == 2 && !clr) continue;
			if (i == 3 && !cll) continue;
			int nx = cx + dx[i], ny = cy + dy[i], nlr = i == 2 ? clr - 1 : clr, nll = i == 3 ? cll - 1 : cll;

			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (d[nx][ny] >= nll) continue;
				if (d[nx][ny] == -1) ++cnt;
				d[nx][ny] = nll;
				q.push({ nx, ny, nll, nlr });
			}
		}
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> l >> r;
	int sx, sy;
	memset(d, -1, sizeof(d));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char c; cin >> c;
			if (c == '1') d[i][j] = 1001;
			else if (c == '2') sx = i, sy = j;
		}
	}

	cout << bfs(sx, sy);
}