[백준 1175] 배달

일트 성공 ㅋ 기부니가 좋다고요~

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

1175번: 배달

#include <cstdio>
#include <queue>
int N, M;
char board[50 + 2][50 + 2];
int visited[50 + 2][50 + 2][4 + 2][3 + 2];	// (좌표) (방향) (어디어디 방문했는지)
int arrv_bit[2] = { 1, 2 };

struct _qt
{
	int x, y;
	int dir;
	int cnt;
	int arrv;
	bool chk[2] = {false, };
};

std::queue<_qt> Q;

struct _st
{
	int x, y;
};

_st C[2];

void input()
{
	scanf("%d %d", &N, &M);
	int num = 0;
	for (int i = 0; i < N; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 'S') {
				Q.push({ i, j, -1, 0 , 0, {false, false} });
				board[i][j] = '.';
			}
			if (board[i][j] == 'C') {
				C[num].x = i;
				C[num].y = j;
				num++;
			}
		}
	}
}

int BFS()
{
	static int dir_x[4] = { 0, 0 ,1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	

	while (!Q.empty()) {
		_qt data = Q.front();
		//printf("(%d %d) [%d] %d %d %d\n", data.x, data.y, data.dir, data.cnt, data.chk[0], data.chk[1]);
		Q.pop();

		if (data.chk[0] == true && data.chk[1] == true) return data.cnt;


		for (int p = 0; p < 4; p++) {
			if (p == data.dir) continue;	// 같은 방향으로 두 번 연속 이동할 수 없다.
			_qt next = data;
			next.x = data.x + dir_x[p];
			next.y = data.y + dir_y[p];
			next.dir = p;
			next.cnt = data.cnt + 1;

			if (next.x < 0 || next.x > N - 1 || next.y < 0 || next.y > M - 1) continue;
			if (visited[next.x][next.y][next.dir][next.arrv]) continue;
			if (board[next.x][next.y] == '#') continue;
			if (board[next.x][next.y] == 'C') {
				int type = -1;
				if (next.x == C[0].x && next.y == C[0].y) type = 0;
				else type = 1;
			
				if (next.chk[type] == true) continue;
				next.chk[type] = true;
				next.arrv += arrv_bit[type];
			}
			visited[next.x][next.y][next.dir][next.arrv] = 1;
			Q.push(next);
		}
	}
	return -1;
}




int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

방향만 따져주어서는 안되는 문제이다.

해당 좌표에 도착했을 때, 몇 군데의 C를 방문했는지 까지 고려해주어야 한다.

따라서 상태 발전을 위한 정보에 (현재좌표(x, y), 현재방향, 이동거리, 몇 군데 방문했는지, 어디 방문했는지) 를 넣어주었다.