어흥
[백준 1175] 배달 (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/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;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 1800] 인터넷 설치 (C++) (0) | 2020.10.04 |
---|---|
[백준 6443] 애너그램 (C++) (0) | 2020.10.04 |
[백준 11451] 팩맨 (C++) (0) | 2020.09.28 |
[백준 1495] 기타리스트 (C++) (0) | 2020.09.28 |
[백준 2886] 자리 전쟁 (C++) (0) | 2020.09.22 |
Comments