์•Œ๊ณ ๋ฆฌ์ฆ˜

  • BFS ์‚ฌ์šฉ
  1. ์‹œ์ž‘ํ• ๋•Œ C๋Š” ๋–จ๊ตฌ๊ณ  ์‹œ์ž‘.
  2. bfs๋ฅผ ์ง„ํ–‰ํ•˜๋Š”๋ฐ ์™ผ์ชฝ, ์˜ค๋ฅธ์ชฝ, ์ค‘๋ ฅ ๋ฐ”๊ฟ”์„œ ๊ฒ€์‚ฌํ•˜๊ณ  ๋–จ๊ตฐ๋‹ค.
    1. ๋–จ์–ด์ง€๋Š” ๋„์ค‘์— D๋ฅผ ๋งŒ๋‚˜๋ฉด, ๋งŒ๋‚ฌ๋‹ค๊ณ  ํ‘œ์‹œ โ†’ ๋๋‚˜๊ณ  ๋ฐ”๋กœ ans ์—…๋ฐ์ดํŠธ
  3. ์ด๋•Œ visit์€ ํ•ด๋‹น ์œ„์น˜์—์„œ ํ•ด๋‹น ์ค‘๋ ฅ์ผ๋•Œ ์ตœ์†Œ flip์„ ์ €์žฅํ•จ
    1. ๋‚˜๋Š” ์ด๋™ํ›„ ๋–จ๊ตฌ๊ธฐ ์ „๊ณผ ๋–จ๊ตฐ ํ›„ ๋‘๊ฐ€์ง€๋งŒ visit ํ‘œ์‹œํ–ˆ์ง€๋งŒ, ๋” ํ•  ์ˆ˜๋„ ์žˆ์„ ๊ฑฐ ๊ฐ™์Œ.
  • ์‹œ๊ฐ„ ๋” ์ค„์ด๊ธฐ
    • ์šฐ์„ ์ˆœ์œ„ ํ ์‚ฌ์šฉํ•˜์—ฌ, flip ํšŸ์ˆ˜๊ฐ€ ์ ์€ ๊ฒƒ์„ ์šฐ์„ ํ•˜๊ธฐ
    • visit ์ฒดํฌ๋ฅผ ๋” ํ•  ์ˆ˜ ์žˆ๋Š” ๋ถ€๋ถ„์€ ๋”ํ•˜๊ธฐ

์ฝ”๋“œ

#include <iostream>
#include <list>
#define INF 2000000000
 
using namespace std;
 
int n, m, os[2] = { 1, -1 }, visit[500][500][2], ans = INF;
char map[500][500];
pair<int, int> c;
list<pair<pair<int, int>, pair<bool, int>>> l;
bool meetD;
 
bool fall(bool g, int* r, int* c);
void bfs();
void afterCheck(int *r, int *c, bool g, int f);
int min(int a, int b) {
	return a < b ? a : b;
}
 
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			map[i][j] = s[j];
			if (s[j] == 'C')
				c = { i, j };
			visit[i][j][0] = visit[i][j][1] = INF;
		}
	}
 
	if (!fall(0, &c.first, &c.second)) {
		cout << -1;
		return 0;
	}
 
	bfs();
	if (ans != INF)
		cout << ans;
	else
		cout << -1;
}
 
bool fall(bool g, int* r, int* c) {
	while (((g == 0 && *r < n - 1) || (g == 1 && *r > 0)) && map[*r + os[g]][*c] != '#') {
		if (map[*r][*c] == 'D')
			meetD = true;
		*r += os[g];
	}
 
	if (map[*r][*c] == 'D')
		meetD = true;
 
	if ((g == 0 && *r == n - 1) || (g == 1 && *r == 0))
		return false;
	return true;
}
 
void bfs() {
	l.push_back({ {c.first, c.second}, {0,0} });
	visit[c.first][c.second][0] = 0;
 
	while (!l.empty()) {
		int cr = l.front().first.first, cc = l.front().first.second, g = l.front().second.first, f = l.front().second.second;
		l.pop_front();
 
		if (map[cr][cc] == 'D') {
			ans = min(ans, f);
			continue;
		}
 
		for (int i = 0; i < 2; i++) {
			int nr = cr, nc = cc + os[i];
			if (nc >= 0 && nc < m && f < visit[nr][nc][g] && map[nr][nc] != '#')
				afterCheck(&nr, &nc, g, f);
		}
 
		if (++f < visit[cr][cc][!g])
			afterCheck(&cr, &cc, !g, f);
	}
}
 
void afterCheck(int* r, int* c, bool g, int f) {
	visit[*r][*c][g] = f;
	bool temp = fall(g, r, c);
 
	if (meetD) {
		meetD = false;
		ans = min(ans, f);
	}
	else if (temp) {
		visit[*r][*c][g] = f;
		l.push_back({ {*r,*c}, {g, f} });
	}
}