2151 ๊ฑฐ์šธ์„ค์น˜

์•Œ๊ณ ๋ฆฌ์ฆ˜ (BFS)

1. ์ž๊ธฐ ๋ฐฉํ–ฅ์œผ๋กœ๋งŒ ์ญ‰ ๊ฐ€๋‹ค๊ฐ€ ! ๋ฅผ ๋งŒ๋‚˜๋ฉด ์ž๊ธฐ๋ฐฉํ–ฅ + ์–‘์˜†์œผ๋กœ ์ด๋™. ์–‘์˜†์œผ๋กœ ์ด๋™ํ•  ๋• ๊ฑฐ์šธ์„ ์„ค์น˜ํ•˜๋Š” ๊ฒƒ์ด๋ฏ€๋กœ ๊ฑฐ์šธ + 1.
2. ์ด๋•Œ visit์œผ๋กœ ์ด๋ฏธ์™”๋˜๊ณณ์„ ์•ˆ๊ฐ€๋ฉด, ๋‹ค๋ฅธ ๋ฃจํŠธ๋กœ ๊ฐ€๋Š” ๋น›์€ ์ค‘๊ฐ„์— ๋Š๊ธฐ๊ธฐ์—, visit์— ๋น›์ด ๊ทธ๊ณณ์— ๋„์ฐฉํ–ˆ์„ ๋•Œ์˜ ๊ฑฐ์šธ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ €์žฅํ•จ.
  ๊ทธ๋ฆฌ๊ณ  ๋‹ค์Œ ๋น›์ด ๊ทธ๊ณณ์— ๋„์ฐฉํ–ˆ์„ ๋•Œ, ๊ฑฐ์šธ ๊ฐœ์ˆ˜๊ฐ€ ์ ์„ ๋•Œ๋งŒ ์ด๋™ ์•„๋‹ˆ๋ฉด ์ด๋™์‹œํ‚ค์ง€ ์•Š๋Š”๋‹ค.
	ex)
		if( ....   &&  n + 1 < visit[r][c])
			visit[r][c] = n + 1
3. ์ด๋•Œ ๋ฌผ๋ก  ๊ฑฐ์šธ์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ๊ทธ๋ƒฅ ์ž๊ธฐ ๋ฐฉํ–ฅ์œผ๋กœ ๊ฐ€๋Š” ๋น›์€ visit ๊ฒ€์‚ฌํ•˜์ง€ ์•Š๋Š”๋‹ค.

์ฝ”๋“œ

#include <bits/stdc++.h>
 
using namespace std;
 
char house[50][50];
int DP[50][50];
list<pair<pair<int, int>, pair<int, int>>> q;
int N, r, c;
 
int BFS();
void nextRC(int* row, int* col, int way);
 
int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			cin >> house[i][j];
			if (house[i][j] == '#') {
				r = i;
				c = j;
			}
			DP[i][j] = 2000000000;
		}
 
	cout << BFS();
}
 
 
int BFS() {
	int result = 2000000000;
 
	if(r > 0 && house[r-1][c] != '*')
		q.push_back({ {r, c}, {1, 0} });
	if (r < N - 1 && house[r + 1][c] != '*')
		q.push_back({ {r, c}, {3, 0} });
	if (c < N - 1 && house[r][c + 1] != '*')
		q.push_back({ {r, c}, {2, 0} });
	if (c > 0 && house[r][c - 1] != '*')
		q.push_back({ {r, c}, {4, 0} });
 
	while (!q.empty()) {
		int row = q.front().first.first, col = q.front().first.second, w = q.front().second.first, n = q.front().second.second;
		q.pop_front();
 
		if (house[row][col] == '#' && !(row == r && col == c)) {
			result = result < n ? result : n;
			continue;
		}
 
		nextRC(&row, &col, w);
 
		//์œ„๋กœ ๊ฐˆ์ˆ˜๋„, ๋А๋‚Œํ‘œ์ผ๊ฒฝ์šฐ ์ขŒ์šฐ ๊ฐ€๋Šฅ
 
		if ((row >= 0 && row <= N - 1) && (col >= 0 && col <= N - 1) && house[row][col] != '*') {
			q.push_back({ {row, col}, {w, n} });
			if (house[row][col] == '!' && n + 1 < DP[row][col]) {
				DP[row][col] = n + 1;
				if (w == 1 || w == 3) {
					q.push_back({ {row, col}, {2, n + 1} });
					q.push_back({ {row, col}, {4, n + 1} });
				}
				else {
					q.push_back({ { row, col }, { 1, n + 1 } });
					q.push_back({ { row, col }, { 3, n + 1 } });
				}
			}
		}
	}
	return result;
}
 
void nextRC(int* row, int* col, int way) {
	if (way == 1)
		*row = (*row) - 1;
	else if (way == 2)
		*col = (*col) + 1;
	else if (way == 3)
		*row = (*row) + 1;
	else if (way == 4)
		*col = (*col) - 1;
}