[G1] 백준 16933번 벽 부수고 이동하기 3 C++ 너비 우선 탐색

리뷰

 

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

벽 부수고 이동하기 문제 중 가장 어려웠던 문제

 

 

전역 변수

1. n : 맵의 세로 변의 길이를 저장할 변수
2. m : 맵의 가로 변의 길이를 저장할 변수
3. k : 벽을 부술 수 있는 횟수를 저장할 변수
4. v : 방문 처리를 진행하기 위한 논리형 3차 배열
5. Pos : 시뮬레이션에 사용할 구조체 위치 좌표 x, y와 소요 시간 t, 벽을 뚫은 횟수 t, 낮/밤 정보 w를 정의한다.
6. dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. print

void print(int cx, int cy, int ct, int ck, int cw) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i == cx && j == cy) cout << '2';
			else {
				cout << lst[i][j];
			}
		}
		cout << "\n";
	}
	cout << ct << " " << ck << " " << cw << "\n";
}

 

디버깅용 함수

1. Pos의 인자들을 매개변수로 입력 받는다.
2. 기본적으로 맵 정보를 출력하고, 현재 위치를 2로 표시해 준다.
3. 맵 정보를 출력 후엔 ct, ck, cw정보를 출력해 준다.

 

2. bfs

int bfs()

 

맵의 좌상단부터 우하단까지 k개 이하의 벽을 부수며 이동하는 최단 거리를 구하는 함수

1. Pos 타입의 큐 q를 초기화 하고, 초기 위치 0, 0과 시작 시간 1, 벽을 부순 갯수 0, 낮을 나타낼 0을 push한다.
2. v에 초기 위치 0, 0과 벽을 부순 갯수 0을 인덱스로 사용하여 방문 처리를 진행한다.
3. q가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 빼내어 준다.
4. 기저 조건으로 현재 위치가 맵의 우하단이라면 ct를 리턴해 준다.
5. 4방향 탐색을 진행하고, 맵의 범위 안에 있으며 방문처리 되지 않은 지역이라면 이동을 진행해 준다.
6. 맵의 값이 '0'이라면 방문처리 후 시간을 증가하여 이동한 좌표 정보를 q에 추가해 준다.
7. 맵의 값이 '1'이라면 별개의 로직을 진행한다, 우선 벽을 부순 횟수를 증가시키고 k보다 크다면 continue처리한다.
8. 만약 현재 w값이 0이라면 낮이므로 이동 진행 후 벽을 부순 개수를 증가시켜 q에 추가해 준다.
9. w값이 1이라면 방문처리를 하지 않고 현재 위치에 시간만 증가시켜 q에 추가해 준다.

 

문제풀이

1. n, m, k값을 입력 받는다.
2. lst배열에 맵 정보를 입력 받아준다.
3. bfs함수를 호출하고 리턴값을 출력해 준다.

 

트러블 슈팅

1. 방향 배열을 현재 위치도 포함하여 문제에 접근했다가 현재 위치가 1인 경우의 예외처리를 하지 못해 틀렸다.
2. 현재 위치가 1인 경우의 예외를 적용했다가 큐에 중복된 요소가 push되어 1% 시간초과를 받았다.
3. 이동할 위치가 1인 경우 현재 위치를 큐에 한번만 push하였으나 방향이 총 4개이므로 17% 시간초과를 받았다.
4. 다익스트라를 활용하여 1을 만난 경우 nt를 2만큼 증가시키는 로직으로 변경하여 AC를 받았다.
5. 가중치가 1로 고정이므로 다익스트라가 아닌 방문 배열로 변경하여 메모리와 시간을 최적화 하였다.
6. 우선순위 큐를 큐로 바꾸고 이동 가능 시 현재 위치를 방문하는 로직으로 변경하여 메모리와 시간을 최적화 하였다.

 

참고 사항

• 이동 시 가중치가 1인 경우 방문 배열을 사용하는 것이 다익스트라 알고리즘을 구현하는 것 보다 빠르다.
• 우선순위 큐가 아닌 큐로 구현할 수 있을 경우 더 빠르게 문제를 풀 수 있다.

 

정답 코드

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

int n, m, k;
string lst[1000];
bool v[1000][1000][11];
struct Pos {
	int x, y, t, k, w;
};
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

void print(int cx, int cy, int ct, int ck, int cw) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i == cx && j == cy) cout << '2';
			else {
				cout << lst[i][j];
			}
		}
		cout << "\n";
	}
	cout << ct << " " << ck << " " << cw << "\n";
}

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

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t, ck = pos.k, cw = pos.w;
		//print(cx, cy, ct, ck, cw);
		if (cx == n - 1 && cy == m - 1) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1, nk = ck + 1, nw = cw ^ 1;
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny][ck]) {
				if (lst[nx][ny] == '0') {
					v[nx][ny][ck] = 1;
					q.push({ nx, ny, nt, ck, nw });
				}
				else {
					if (nk > k) continue;
					if (!cw) {
						v[nx][ny][ck] = 1;
						q.push({ nx, ny, nt, nk, nw });
					}
					else q.push({ cx, cy, nt, ck, nw });
				}
			}
		}
	}
	return -1;
}

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

	cin >> n >> m >> k;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	cout << bfs();
}