[G4] 백준 25417번 고속의 숫자 탐색 C++ 너비 우선 탐색

리뷰

 

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

왠진 모르겠는데 조건문에 ||와 &&를 섞어서 작성 후 제출했었다 어이없게 두번을 틀렸다.

 

 

전역 변수

• lst : 맵 정보를 저장할 2차원 배열
• v : 방문 정보를 체크할 2차원 배열
• Pos : 현재 위치 x, y와 소요 시간 t를 정의할 구조체, t를 기준으로 오름차순 정렬한다.
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. bfs

int bfs(int sx, int sy)

 

너비 우선 탐색을 통해 출발지 부터 도착지 까지 이동 하는 최소 시간을 구하는 함수

1. 매개 변수로 시작 위치의 좌표 sx, sy를 전달 받는다.
2. Pos타입의 우선순위 큐 pq를 초기화 하고, 초기 위치 sx, sy와 소요 시간 0을 push해준다.
3. v배열에 시작 위치를 방문처리를 진행해 준다.
4. pq가 빌 때 까지 while 루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
5. 기저 조건으로 목표 위치에 도달한 경우 소요 시간 ct를 리턴해 준다.
6. 4방향 탐색을 진행하고, 맵의 범위 내에 있으며, 방문 처리되어 있지 않고, -1이 아니라면 이동을 진행한다.
7. 이동 후엔 방문처리 후 이동한 위치와 소요 시간을 증가시킨 후 pq에 push해준다.
8. 이후 해당 방향으로 쭉 진행을 이어준다.
9. 맵의 범위를 벗어난 경우 벗어나기 전의 위치에 방문처리가 되어있지 않다면 이동을 진행한다.
10. -1을 만난 경우 만나기 전의 위치에 방문처리가 되어있지 않다면 이동을 진행한다.
11. 이동한 위치가 맵 상에서 7이고, 해당 위치에 방문처리가 되어있지 않다면 이동을 진행한다.
12. 각 케이스에 해당하는 위치에 방문처리 및 pq에 push를 진행하고, break처리해 준다.
13. while 루프가 종료될 때 까지 기저 조건에 도달하지 못한다면 -1을 리턴해 준다.

2. print

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

 

디버깅용 함수

 

문제풀이

1. 5 * 5 맵 정보를 lst배열에 입력 받아준다.
2. 시작 위치의 좌표 sx, sy에 값을 입력 받고, bfs함수에 매개변수로 전달하여 값을 리턴 받는다.
3. 리턴받은 값을 출력해 준다.

 

트러블 슈팅

1. 예제는 다 맞는데 제출 시 14%에서 계속 틀리게 되었다.
2. 범위 체크를 해주는 로직에서 || 한개를 &&로 작성해 준게 원인이었다, 고치고 나니 AC를 받았다.

 

참고 사항

• 그냥 queue를 사용해 주니 한 방향으로 쭉 진행하였을 때 그리디하지 못한 것 같아 pq로 변경해 주었다.

 

정답 코드

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

int lst[5][5];
bool v[5][5];
struct Pos {
	int x, y, t;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void print(int x, int y, int t) {
	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 5; ++j) {
			if (x == i && y == j) cout << 8 << " ";
			else cout << lst[i][j] << " ";
		}
		cout << "\n";
	}
	cout << x << " " << y << " " << t << "\n";
}

int bfs(int sx, int sy) {
	priority_queue<Pos> pq;
	pq.push({ sx, sy, 0 });
	v[sx][sy] = true;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t;
		//print(cx, cy, ct);
		if (lst[cx][cy] == 1) return ct;

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

				while (1) {
					if (0 > nx || nx >= 5 || 0 > ny || ny >= 5) {
						int nnx = nx - dx[i], nny = ny - dy[i];
						//cout << nx << " " << ny << " " << nnx << " " << nny << "\n";
						if (!v[nnx][nny]) {
							v[nnx][nny] = true;
							pq.push({ nnx, nny, nt });
						}
						break;
					}
					if (lst[nx][ny] == -1) {
						int nnx = nx - dx[i], nny = ny - dy[i];
						if (!v[nnx][nny]) {
							v[nnx][nny] = true;
							pq.push({ nnx, nny, nt });
						}
						break;
					}
					if (lst[nx][ny] == 7) {
						if (!v[nx][ny]) {
							v[nx][ny] = true;
							pq.push({ nx, ny, nt });
						}
						break;
					}

					nx += dx[i];
					ny += dy[i];
				}
			}
		}
	}
	return -1;
}

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

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