[백준][C++] 1175. 배달

 

문제는 간단해보였는데 생각보다 너무 오래걸렸다...

 

1) 도착점 C가 2개인 점

2) 같은 방향으로 2번 연속 이동할 수 없다는 점

3) 방문했던 점도 다시 방문할 수 있다는 점

 

이 세 조건을 만족시키면서 BFS를 수행하면 된다.

사실 1, 3번 때문에 많이 헤맸다...

 

C가 2개이기 때문에 두 점이 명확히 구분되도록 하나는 C, 다른 하나는 D로 바꿔주었다.

또한 S도 2번 이상 방문될 수 있기 때문에 S의 좌표는 따로 저장해놓은 다음 .으로 바꿔주었다.

 

visited 배열은 5차원 배열로 구체화시켜서 같은 상태로 중복 방문을 할 수 없도록 했다.

visited[MAX][MAX][dir][C][D]

 

예를 들어 visited[3][4][2][0][1] = 1이면, (3, 4) 지점을 왼쪽에서 진입한 상태이고, C는 방문하지 않고 D만 방문했다는 뜻이다. 

 

마지막에 주의할 점은, 선물을 모두 배달하는 것이 불가능할 경우 -1을 출력해야 한다는 것이다. (이거 때문에 또 삽질함..)

 

// 1175_배달.cpp
using namespace std;
#include <iostream>;
#include <queue>
#include <algorithm>
#include <string>
#define MAX 50

struct point {
	int x, y; // 좌표
	int dir;
	int c, d;
};

int n, m;
int answer = 0; // 최소 시간

int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
int visited[MAX][MAX][5][2][2] = { 0, }; // x, y, dir, C, D
char map[MAX][MAX] = { 0, };


void bfs(int sx, int sy) {
	queue<pair<point, int>> q;

	visited[sx][sy][4][0][0] = 1;

	point start;
	start.x = sx;
	start.y = sy;
	start.dir = 4;
	start.c = 0;
	start.d = 0;
	int count = 0;

	q.emplace(start, count);

	while (!q.empty()) {
		point p = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (p.c == 1 && p.d == 1) {
			answer = cnt;
			break;
		}

		for (int i = 0; i < 4; i++) {
			if (p.dir == i) continue; // 방향 같으면 continue

			point np = p;
			np.x = p.x + dir[i][0];
			np.y = p.y + dir[i][1];
			np.dir = i;

			if (np.x < 0 || np.y < 0 || np.x >= n || np.y >= m) continue;
			if (visited[np.x][np.y][i][np.c][np.d] || map[np.x][np.y] == '#') continue;

			if (map[np.x][np.y] == 'C') np.c = 1;
			if (map[np.x][np.y] == 'D') np.d = 1;

			visited[np.x][np.y][np.dir][np.c][np.d] = 1;
			q.emplace(np, cnt + 1);
		}
	}
}

int main() {
	int sx, sy;
	int num = 0; // C의 개수
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %c", &map[i][j]);

			if (map[i][j] == 'S') {
				sx = i;
				sy = j;
				map[i][j] = '.'; // 시작점도 거칠 수 있으므로 .으로 바꿔줌
			}
			else if (map[i][j] == 'C') {
				num++;
				if (num == 2) {
					map[i][j] = 'D';
				}
			}
		}
	}

	bfs(sx, sy);

	if (answer == 0) printf("-1\n"); // 불가능하면 -1 출력
	else printf("%d\n", answer);

	return 0;
}