[G1] 백준 23817번 포항항 C++ 너비 우선 탐색, 백트래킹

리뷰

 

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

비트마스킹으로 접근했다가 시간 초과를 맞고, BFS + 백트래킹 구조로 접근하니 AC를 받았다.

하지만 실행 시간이 너무 긴 것 같아 만족스럽지는 못한 풀이

 

 

전역 변수

• n, m : 맵의 세로/가로의 길이를 저장할 변수
• idx : 식당의 인덱스를 저장할 변수
• ans : 정답을 저장할 변수
• lst : 맵 정보를 정수로 치환할 2차원 배열
• v : 맵의 방문 여부를 체크할 2차원 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 시뮬레이션 시 사용할 위치 x, y와 소요 시간 t를 정의할 구조체
• Edge : 간선 저장 시 사용할 식당의 인덱스 idx와 거리 t를 정의할 구조체
• edges : 인접 리스트를 저장할 Edge타입 벡터의 배열
• starts : 각 식당의 위치 좌표를 저장할 Pos타입의 배열
• pv : 식당의 방문 여부를 저장할 배열

 

함수

1. bfs

void bfs(int index, Pos start)

 

시작 지점과 각 식당에서 다른 위치까지 걸리는 시간을 구하고 인접 리스트를 초기화할 함수

1. 매개 변수로 현재 식당의 index와 초기 위치 start를 전달 받는다.
2. Pos타입의 큐 q를 초기화 하고, 초기 위치와 소요 시간 0을 push해주고, 방문 처리를 해준다.
3. q가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
4. 4방향 탐색을 진행하고, 범위 내에 있으며 장애물이 아니고 방문하지 않은 곳이라면 이동을 진행한다.
5. 이동 후엔 방문처리 후 만약 이동한 위치가 식당이라면 인접 리스트에 식당 인덱스와 거리를 추가해 준다.
6. 큐에 이동한 위치와 시간을 추가해 주고 탐색을 계속 진행해 준다.

 

2. bt

void bt(int level, int node, int sum)

 

백트래킹을 통해 5개의 식당을 걸린 최소 시간을 구하기 위한 함수

1. 매개 변수로 방문한 식당 개수 level, 현재 식당 인덱스 node, 거리의 합 sum을 전달 받는다.
2. 첫 번째 기저 조건으로 ans가 sum이하일 경우 탐색을 중단하고 리턴해 준다.
3. 두 번째 기저 조건으로 level이 5에 도달한 경우 ans와 sum을 비교해 작은 값을 ans로 저장하고 리턴해 준다.
4. 현재 node의 인접리스트를 순회하며 방문하지 않은 식당이 있을 경우 방문처리 후 재귀를 진행한다.
5. 이 때 level + 1, 이동한 식당, sum + 거리를 매개변수로 전달하고, 재귀를 빠져나오며 방문 체크를 해제한다.

 

문제풀이

1. n, m값을 입력 받고, n * m크기의 맵 정보를 입력 받아준다.
2. 입력 받은 문자가 '.'라면 lst배열에 0, 'X'라면 -1로 저장해 준다.
3. 'K'라면 lst배열에 idx를 전위 증가 시킨 값을 저장하고, starts배열의 idx인덱스에 위치를 저장해 준다.
4. 'S'라면 lst배열에 1로 저장해 주고, starts배열의 1번 인덱스에 위치를 저장해 준다.
5. 만약 idx가 6미만인 경우 식당이 5개가 안되는 것이므로 -1을 출력 후 리턴해 준다.
6. 1 ~ idx번째 starts배열의 값을 bfs함수로 순회하며 인접리스트를 초기화 해준다.
7. pv배열의 1번을 방문처리 후 bt함수에 0, 1, 0을 인자로 전달해 백트래킹을 진행해준다.
8. 모든 탐색을 마친 후 ans의 값이 초기값이라면 -1을, 아니라면 ans를 출력해 준다.

 

트러블 슈팅

1. 식당의 위치를 2의 제곱으로 저장해 해시맵의 key를 활용한 비트마스킹을 통한 풀이를 진행하였으나 시간 초과를 받게 되었다, 최대 1000 * 1000 * 21번의 탐색이라 생각했었는데 그 보다 더 큰 시간 복잡도를 요구했다.
2. 결국 시작점 및 각 식당에서 다른 식당으로의 거리를 인접 리스트화 하고 백트래킹 + 가지치기를 통해 5개 식당을 방문하는 최소값을 구했더니 AC를 받았다.

 

참고 사항

없음

 

 

정답 코드

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

int n, m, idx = 1, ans = 2e9;
int lst[1000][1000];
bool v[1000][1000];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int x, y, t;
};
struct Edge {
	int idx, t;
};
vector<Edge> edges[22];
Pos starts[22];
bool pv[22];

void bfs(int index, Pos start) {
	queue<Pos> q;
	q.push({ start.x, start.y, 0 });
	v[start.x][start.y] = true;

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

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1;
			if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != -1 && !v[nx][ny]) {
				v[nx][ny] = true;
				if (lst[nx][ny]) edges[index].push_back({ lst[nx][ny], nt });
				q.push({ nx, ny, nt });
			}
		}
	}
}

void bt(int level, int node, int sum) {
	if (ans <= sum) return;
	if (level == 5) {
		ans = min(ans, sum);
		return;
	}

	for (const Edge& e : edges[node]) {
		if (pv[e.idx]) continue;
		pv[e.idx] = true;
		bt(level + 1, e.idx, sum + e.t);
		pv[e.idx] = false;
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char ch; cin >> ch;
			if (ch == '.') lst[i][j] = 0;
			else if (ch == 'X') lst[i][j] = -1;
			else if (ch == 'K') {
				lst[i][j] = ++idx;
				starts[idx] = { i, j };
			}
			else {
				lst[i][j] = 1;
				starts[1] = { i, j };
			}
		}
	}

	if (idx < 6) {
		cout << -1;
		return 0;
	}

	for (int i = 1; i <= idx; ++i) {
		memset(v, 0, sizeof(v));
		bfs(i, starts[i]);
	}
	
	pv[1] = true;
	bt(0, 1, 0);

	if (ans == 2e9) cout << -1;
	else cout << ans;
}