[BAE/<JOON> 문제풀이] 1175. 배달

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

1175번: 배달

핵심::

진입 방향에 따라서 거리 따로 계산

 

풀이::

같은 방향으로 2번 이상 나아갈 수 없으므로 어떤 지점의 최솟값을 기록할 때  들어가는 방향도 고려해야한다. 

 

다음과 같은 경우를 생각해보면 쉽게 이해할 수 있다.

빨간 타일에서 1번 방향으로 움직인 거리를 기록할 때 3번 방향에서 들어왔을 때의 최솟값은 고려하면 안된다. 

 

하지만 만약 타일 당 하나의 최소거리를 기록한다면 3번 타일까지의 거리가 가장 가까웠을 경우, 1번 타일 거리는

 

3번 타일을 거쳐간 거리로 기록될 것이다.

 

이러한 오류를 피하기 위해서 타일당 4개의 진입 방향에 따라서 최소 거리들을 따로 기록하여 저장해야 한다.

 

이러한 주의점 외에는 일반적인 BFS 풀이와 다른 점이 없다.

 

의견::

얘도 골드1치고는 쉬운 편인 것 같다. 같은 BFS문제인 열쇠 문제하고 난이도 차이가 많이 나는 듯

 

코드::

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

struct node {
	int x, y, pd, cnt;
};

struct ti {
	int c[4] = { 2100000000, 2100000000, 2100000000, 2100000000 };
};

int mvx[4] = { 1, 0, -1, 0 };
int mvy[4] = { 0, 1, 0, -1 };

int main()
{
	int n, m;	
	cin >> n >> m;
	vector<vector<int>> arr(n + 1, vector<int>(m + 1));
	vector<vector<ti>> cnt(n + 1, vector<ti>(m + 1));
	int sx, sy;
	for (int i = 1; i <= n; i++) {
		string ss; cin >> ss;
		for (int j = 1; j <= m; j++) {
			switch (ss[j - 1]) {
			case '.' :
				arr[i][j] = 0;
				break;
			case '#' :
				arr[i][j] = 1;
				break;
			case 'S' :
				sx = i; sy = j;
				arr[i][j] = 0;
				break;
			case 'C':
				arr[i][j] = 2;
				break;
			}
		}
	}

	queue<node> q;
	q.push({ sx, sy, -2, 0 });
	cnt[sx][sy] = { 0, };
	node s2 = { -1, -1, -1, -1 };
	while (!q.empty()) {
		const auto current = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			if (current.pd == i) continue; // 이전 방향과 같을 경우에는 탐색하지 않음
			int mx = current.x + mvx[i];
			int my = current.y + mvy[i];
			if (mx > n || mx < 1 || my > m || my < 1 || arr[mx][my] == 1 || cnt[mx][my].c[i] <= current.cnt + 1) continue;
			if (arr[mx][my] == 2) {
				//첫번째 배달 지점 및 방향/거리 저장
				s2 = { mx, my, i, current.cnt + 1 };
				break;
			}
			cnt[mx][my].c[i] = current.cnt + 1;
			q.push({ mx, my, i, current.cnt + 1 });
		}

		if (s2.x != -1) break;
	}

	// 첫번째 배달 지점을 찾지 못했다면 실패
	if (s2.x == -1) {
		cout << -1;
		return 0;
	}
	arr[s2.x][s2.y] = 0;
	cnt = vector<vector<ti>>(n + 1, vector<ti>(m + 1));
	cnt[s2.x][s2.y].c[s2.pd] = s2.cnt;
	q = queue<node>();
	q.push(s2);
	while (!q.empty()) {
		const auto current = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			if (current.pd == i) continue;
			int mx = current.x + mvx[i];
			int my = current.y + mvy[i];
			if (mx > n || mx < 1 || my > m || my < 1 || arr[mx][my] == 1 || cnt[mx][my].c[i] <= current.cnt + 1) continue;
			if (arr[mx][my] == 2) {
				// 배달 완료
				cout << current.cnt + 1;
				return 0;
			}
			cnt[mx][my].c[i] = current.cnt + 1;
			q.push({ mx, my, i, current.cnt + 1 });
		}
	}

	//두번째 배달 지점을 찾지 못했으므로 실패
	cout << -1;
	return 0;
}