[백준 1175] 배달 (C++)

문제 링크: www.acmicpc.net/problem/1175

1175번: 배달

1. 주의할 점

- 4차 배열을 사용하여 해당 지점에(y,x) 직전에 어떤 방향으로 도착했으며(dir), 현재까지 배달을 완료한 장소(del: 단, 장소를 구분해야 하므로 한곳: +1, 다른곳: +2) -> 비트마스킹이라고 생각하면 된다

- 구조체를 사용하여 현재 위치, 방향, 현재까지 배달을 완료한 장소, 현재까지의 이동거리를 저장한다

 

2. 구현

- 배달을 해야하는 장소(C)를 Deliver 벡터에 저장한다

- 모든 Check[][][][] 배열의 값을 큰 값으로 초기화한다

- 시작점을 Queue에 넣고 시작하며, 시작점에선 이전 방향의 영향을 받지 않도록 dir값을 -1로 설정한다

- BFS를 통해 다음 지점으로 이동하며, cdel의 값이 3이면(모두 배달 완료) Result값을 초기화한다. 이동 조건은 다음과 같다

[이동 조건] -> 글보단 코드를 통해 이해하자(말로 설명하기 까다롭다)

- 다음 칸이 . 이고, 해당 칸으로 이동시 cdel의 값을 가지고 cv+1만큼 큰 값으로 방문을 했다면, 재방문하며 Check[][][][]값을 초기화한다

- 다음 칸이 C이고, 이미 방문한 배달 필수 지점이 아니라면, cdel+plus의 값을 가지고 cv+1만큼 큰 값으로 방문을 했다면, 재방문하며 Check[][][][]값을 초기화한다

 

#include <iostream>
#include <queue>
#include <vector>
#include <math.h>
using namespace std;
struct info {
	int x, y, dir, del, val;
};
info tmp;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
char arr[50][50];
int check[50][50][4][4];		//y,x,dir,deliver 성공 수
int row, col;
vector<info> deliver;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	queue<info> q;
	cin >> row >> col;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			for (int m = 0; m < 4; m++) 
				for(int l=0;l<4;l++)
					check[i][j][m][l] = 987654321;			
			cin >> arr[i][j];
			if (arr[i][j] == 'S') {
				arr[i][j] = '.';
				tmp.x = j;
				tmp.y = i;
				tmp.dir = -1;
				tmp.val = 0;
				tmp.del = 0;
				q.push(tmp);
				for (int k = 0; k < 4; k++)
					check[i][j][k][0] = 0;
			}
			else if (arr[i][j] == 'C') {
				tmp.x = j;
				tmp.y = i;
				deliver.push_back(tmp);
			}
		}
	int result = -1;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cd = q.front().dir;
		int cdel = q.front().del;
		int cv = q.front().val;
		q.pop();
		if (cdel == 3) {
			result = cv;
			break;
		}
		for (int i = 0; i < 4; i++) {
			if (i == cd) continue;
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			char nv = arr[ny][nx];
			if (nx >= 0 && ny >= 0 && nx < col && ny < row && nv != '#') {
				if (nv == '.' && check[ny][nx][i][cdel]>cv+1) {
					check[ny][nx][i][cdel] = cv + 1;
					tmp.x = nx;
					tmp.y = ny;
					tmp.del = cdel;
					tmp.val = cv + 1;
					tmp.dir = i;
					q.push(tmp);
				}
				else if (nv == 'C') {
					int plus = 0;
					for (int k = 0; k < deliver.size(); k++) {
						if (nx == deliver[k].x && ny == deliver[k].y) {
							plus = pow(2, k);
							break;
						}
					}
					if (cdel != plus && check[ny][nx][i][cdel + plus] > cv + 1) {
						check[ny][nx][i][cdel + plus] = cv + 1;
						tmp.x = nx;
						tmp.y = ny;
						tmp.del = cdel + plus;
						tmp.val = cv + 1;
						tmp.dir = i;
						q.push(tmp);
					}
				}
			}
		}
	}
	cout << result;
	return 0;
}