백준2206 - 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

다익스트라를 이용하여 풀었다. 디큐를 사용하였고 벽을 부수기 전에 이동한 것을 push_front를 이용하여 벽을 부순 후 이동한 것 보다 먼저 처리하였다. 벽을 부순 후 이동한 것은 push_back으로 나중에 처리되도록 하였다.

 

#include <iostream>
#include <deque>
#include <string>
#define MAX 1001
using namespace std;

class Point {
public:
	int x, y, z; //x, y는 현재 위치, z는 벽을 전에 한번 부셨는지 여부(0이면 통과X, 1이면 통과O)
	Point(int x, int y, int z) {
		this->x = x;
		this->y = y;
		this->z = z;
	}
};

//벽 방문 횟수를 담을 공간 설정

int m, n;
int mat[MAX][MAX]; //좌표 정보
int d[MAX][MAX]; //각각의 칸마다 비용 정보

//상하좌우
int dx[] = { 1,-1,0,0, };
int dy[] = { 0,0,1,-1 };

string s; //문제에서 string으로 주어짐

void dijkstra() {
	deque<Point> q;
	q.push_front(Point(1, 1, 0)); //출발 할때는 벽을 거친적이 없으니까 0으로 세팅
	d[1][1] = 1; //출발지의 비용은 1로 설정

	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int z = q.front().z;
		q.pop_front(); 

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (1 <= nx && nx <= m && 1 <= ny && ny <= n) {
				if (mat[nx][ny] == 1) { //이동하려는 위치가 벽이면
					if (z == 1) { //벽을 한번이라도 거쳤으면
						continue; //무시
					}
					else { //벽을 한번도 거친 적이 없으면
						if (d[nx][ny] > d[x][y] + 1) { //이동하려는 곳의 이미 도달한 비용보다 현재 비용 + 1이 더 싸면
							d[nx][ny] = d[x][y] + 1; //현재 비용 + 1로 갱신
							q.push_back(Point(nx, ny, 1)); //가려는 곳의 위치를 뒤로 넣는다.
						}
					}
				}
				else { //이동하려는 곳이 길이면
					if (z == 1) { //벽을 한번이라도 거쳤으면
						if (d[nx][ny] > d[x][y] + 1) { //이동하려는 곳의 이미 도달한 비용보다 현재 비용 + 1이 더 싸면
							d[nx][ny] = d[x][y] + 1; //현재 비용 + 1로 갱신
							q.push_back(Point(nx, ny, 1)); //가려는 곳의 위치를 뒤로 넣는다.
						}
					}
					else { //벽을 한번이라도 거친 적이 없으면
						if (d[nx][ny] > d[x][y] + 1) { //이동하려는 곳의 이미 도달한 비용보다 현재 비용 + 1이 더 싸면
							d[nx][ny] = d[x][y] + 1; //현재 비용 + 1로 갱신
							q.push_front(Point(nx, ny, 0)); //가려는 곳의 위치를 뒤로 넣는다.
						}
					}
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> m >> n;
	for (int i = 1; i <= m; i++) {
		cin >> s;
		for (int j = 0; j < n; j++) {
			mat[i][j + 1] = s[j] - '0';
			d[i][j + 1] = 987654321; //매우 큰 값으로 초기 비용을 세팅
		}
	}

	dijkstra();

	if (d[m][n] == 987654321) { //도달 못했으면
		cout << -1; //-1 출력
	}
	else { //도달 했으면
		cout << d[m][n]; //비용 출력
	}
}