[G3] 백준 1726번 로봇 C++ 다익스트라, 너비 우선 탐색

리뷰

 

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

문제 조건을 잘 읽자..

 

 

전역 변수

n : 맵의 세로 길이를 저장할 변수

m : 맵의 가로 길이를 저장할 변수

lst : 맵 정보를 저장할 배열

dx, dy : 4방향 탐색을 위한 방향 배열

Pos : 시뮬레이션 시 사용할 구조체 좌표 x, y, 소요 시간 t, 방향 d를 정의한다. t를 기준으로 오름차순으로 정렬한다.

 

함수

1. bfs

int bfs()

 

시작 지점/방향 부터 목표 지점/방향 까지의 최단 경로를 구하기 위한 함수

1. Pos타입의 우선순위 큐 pq를 초기화 한다.
2. pq에 sx, sy, 0, sd를 push해준다, 변수의 경우 전위 감소 시켜주어 0-based-index를 적용해 주었다.
3. n * m * 4 크기의 벡터 dist에 매우 큰 값을 저장해 준다.
4. 시작 위치 및 방향의 dist벡터 값을 0으로 초기화 해준다.
5. pq가 빌 때 까지 while루프를 돌리고, 매 루프마다 요소를 한개씩 뽑아준다.
6. 현재 방향이 2, 3이라면 변수 nd1을 0으로, 변수 nd2를 1로 저장해 준다.
7. 현재 방향이 0, 1이라면 변수 nd1을 2으로, 변수 nd2를 3로 저장해 준다.
8. 현재 위치의 nd1, nd2방향이 현재 시간 + 1보다 크다면 값을 갱신해 주고 pq에 push해준다.
9. 현재 위치에서 현재 방향으로 1, 2, 3칸을 이동하고 맵의 범위 안에 있다면 이동을 진행한다.
10. 만약 벽을 만난 경우 break를 처리해 더 이상 진행하지 못하도록 해준다.
11. 이동한 위치가 현재 시간 + 1보다 크다면 값을 갱신해 주고 pq에 push해준다.
12. 모든 경우를 탐색한 후  0-based-index를 적용한 dist벡터의 목표 지점 및 방향의 값을 리턴해 준다.

 

2. print

void print(int x, int y, int t, int d)

 

시뮬레이션 디버깅용 함수

 

문제풀이

1. n, m값을 입력 받고, lst배열에 맵 정보를 입력 받아준다.
2. 시작 위치와 방향, 목표 위치와 방향을 입력 받아준다.
3. bfs함수를 호출하고 전달 받은 리턴값을 출력해 준다.

 

트러블 슈팅

1. 문제에서 주어진 방향은 동서남북 순서이다, +3, +5증가 후 %4로 모듈러 연산을 통해 접근하였다가 Fail을 받았다.
2. 문제 이해 자체를 잘못했다, 직진의 경우 해당 방향으로 쭉 이동하는게 아닌 1, 2, 3칸 만큼 움직일 수 있다.
3. 로직 수정 후에도 예제의 답이 6이 출력되었다. 진행 중 벽을 만난 경우 break처리해 주니 AC를 받았다.

 

참고 사항

• 맵의 좌표와 방향 정보가 1-based-index로 주어지므로 성향에 맞게 올바르게 값을 파싱해 주어야 한다.

 

정답 코드

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

int n, m;
int sx, sy, sd, ex, ey, ed;
int lst[100][100];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
struct Pos {
	int x, y, t, d;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};

void print(int x, int y, int t, int d) {
	cout << "\n";
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (x == i && y == j) {
				if (d == 0) cout << "→ ";
				if (d == 1) cout << "← ";
				if (d == 2) cout << "↓ ";
				if (d == 3) cout << "↑ ";
			}
			else cout << lst[i][j] << " ";
		}
		cout << "\n";
	}
	cout << t << " " << d << "\n";
}

int bfs() {
	priority_queue<Pos> pq;
	pq.push({ --sx, --sy, 0, --sd });
	vector<vector<vector<int>>> dist(n, vector<vector<int>>(m, vector<int>(4, 2e9)));
	dist[sx][sy][sd] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t, cd = pos.d;
		//print(cx, cy, ct, cd);

		int nd1 = cd == 2 || cd == 3 ? 0 : 2;
		int nd2 = cd == 2 || cd == 3 ? 1 : 3;
		
		if (dist[cx][cy][nd1] > ct + 1) {
			dist[cx][cy][nd1] = ct + 1;
			pq.push({ cx, cy, ct + 1, nd1 });
		}

		for (int i = 1; i <= 3; ++i) {
			int nx = cx + dx[cd] * i, ny = cy + dy[cd] * i;
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (lst[nx][ny]) break;
				if (dist[nx][ny][cd] > ct + 1) {
					dist[nx][ny][cd] = ct + 1;
					pq.push({ nx, ny, ct + 1, cd });
				}
			}
		}

		if (dist[cx][cy][nd2] > ct + 1) {
			dist[cx][cy][nd2] = ct + 1;
			pq.push({ cx, cy, ct + 1, nd2 });
		}
	}
	return dist[--ex][--ey][--ed];
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> lst[i][j];

	cin >> sx >> sy >> sd >> ex >> ey >> ed;
	cout << bfs();
}