[ boj : 23563 ] 벽 타기

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

23563번: 벽 타기

해설 : 루시우가 한칸 움직일때마다 1초씩 시간이 늘지만 벽을 타면 0초라는 걸 보고 일반적인 BFS 문제로는 풀기 힘들지 않을까? 라는 의문점을 가져야 합니다.

결국 이건 쉽게 생각해보면 간선의 가중치가 일정하지 않는 그래프에서 최단거리를 구하는 문제이니 그냥 다익스트라 문제입니다.

문제에서 나와있는 조건대로 코드를 작성해주면 됩니다.

벽을 타고 지나가는 부분만 조심히 잘 처리해주면 되겠군요.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

struct info {
	int x, y, w;
	bool operator<(const info& cur) const {
		return w > cur.w;
	}
};

int n, m;
string board[510];
int memo[510][510];
int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };

void solve();
int djik(int sx, int sy, int ex, int ey);
int check_wall(int x, int y);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	while (t--)solve();
	return 0;
}
void solve()
{
	int sx, sy, ex, ey;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> board[i];
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 'S')
				sx = i, sy = j;
			else if (board[i][j] == 'E')
				ex = i, ey = j;
		}
	}
	cout << djik(sx, sy, ex, ey);
}
int djik(int sx, int sy, int ex, int ey)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			memo[i][j] = (int)1e9;

	priority_queue<info> pq;
	pq.push({ sx,sy,0 });
	memo[sx][sy] = 0;

	while (!pq.empty())
	{
		info cur = pq.top();
		pq.pop();

		if (memo[cur.x][cur.y] < cur.w)continue;

		int cflag = check_wall(cur.x, cur.y);
		for (int i = 0; i < 4; i++) {
			int tx = cur.x + dx[i];
			int ty = cur.y + dy[i];

			if (tx <= 0 || tx >= n - 1 || ty <= 0 || ty >= m - 1 || board[tx][ty]=='#')continue;

			int tflag = check_wall(tx, ty);

			if (cflag && tflag) {
				if (memo[tx][ty] > memo[cur.x][cur.y]) {
					memo[tx][ty] = memo[cur.x][cur.y];
					pq.push({ tx,ty,memo[tx][ty] });
				}
			}
			else {
				if (memo[tx][ty] > memo[cur.x][cur.y] + 1) {
					memo[tx][ty] = memo[cur.x][cur.y] + 1;
					pq.push({ tx,ty,memo[tx][ty] });
				}
			}
		}
	}
	return memo[ex][ey];
}
int check_wall(int x, int y)
{
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		if (board[x + dx[i]][y + dy[i]] == '#')
			cnt++;
	}
	return cnt > 0 ? 1 : 0;
}