[G1] 백준 1175번 배달 C++ 너비 우선 탐색

리뷰

 

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

배달지 두 곳에 배달을 하는 최소 시간을 구하되, 한 방향으로 연속 두번 이동할 수 없는 제약이 있는 문제

 

 

전역 변수

• n, m : 맵의 세로가로 길이를 저장할 변수
• sx, sy : 초기 x, y좌표를 저장할 변수
• lst : 맵 정보를 입력 받을 배열
• v : 방문 여부를 체크하기 위한 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 시뮬레이션 시 현재 위치x, y, 소요 시간 t, 전에 이동한 방향 d, 배달 여부 c를 정의할 구조체
• dic : key를 배달지의 좌표, value를 배달 여부 체크값을 저장할 해시맵

 

함수

1. bfs

int bfs()

 

너비 우선 탐색을 통해 배달지 두 곳에 배달을 마치는 최소 시간을 구하기 위한 함수

1. Pos타입의 q를 초기화 하고, 시작 위치 sx, sy, 소요 시간 0, 전에 이동한 방향 -1, 배달 여부 0을 push한다.
2. v배열에 좌표, 소요 시간, 이동 방향을 인덱스로 활용해 true로 방문 처리를 진행해 준다.
3. q가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
4. 기저 조건으로 만약 현재 배달 여부 cc가 3이라면 현재 소요 시간 ct를 리턴해 준다.
5. 4방향 탐색을 진행하고, 전에 이동한 방향과 일치할 경우 continue처리를 진행해 준다.
6. 맵의 범위 안에 있으면서 이동할 수 있는 곳이라면 이동을 진행해 준다.
7. 이동한 지역이 배달지이며, cc와 이동지의 value를 비트연산한 값이 0이라면 nc에 value만큼 더해준다.
8. 만약 이동 위치 nx, ny, 이동 후 배달 여부 nc, 현재 방향 i가 방문처리 되어 있다면 continue처리해 준다.
9. 아니라면 방문처리 후 q에 push해준다.

 

문제풀이

1. n, m값을 입력 받고, 변수 idx를 1로 초기화 해준다.
2. n * m크기의 맵 정보를 입력 받고, 'S'라면 sx, sy에 시작 위치를 저장하고 이동할 수 있는 땅 '.'로 변경해 준다.
3. 만약 'C'일 경우 해시맵 dic에 위치를 key로, value를 idx로 저장하고 후위 증가시켜준다.
4. bfs함수를 호출하고 리턴받은 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 위치 뿐만 아니라 방향, 배달 여부에 따른 방문 처리를 동시에 진행해 주어야 한다.

 

정답 코드

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

int n, m, sx, sy;
string lst[50];
bool v[50][50][4][5];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int x, y, t, d, c;
};
unordered_map<int, int> dic;

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

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t, cd = pos.d, cc = pos.c;
		if (cc == 3) return ct;

		for (int i = 0; i < 4; ++i) {
			if (i == cd) continue;
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1, nc = cc;
			if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != '#') {
				if (lst[nx][ny] == 'C' && !(cc & dic[nx * m + ny])) nc += dic[nx * m + ny];
				if (v[nx][ny][nc][i]) continue;
				v[nx][ny][nc][i] = true;
				q.push({ nx, ny, nt, i, nc });
			}
		}
	}
	return -1;
}

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

	cin >> n >> m;
	int idx = 1;
	for (int i = 0; i < n; ++i) {
		cin >> lst[i];
		for (int j = 0; j < m; ++j) {
			if (lst[i][j] == 'S') {
				sx = i, sy = j;
				lst[i][j] = '.';
			}
			else if (lst[i][j] == 'C') dic[i * m + j] = idx++;
		}
	}
	cout << bfs();
}