백준1261 - 알고스팟

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

1261번: 알고스팟

처음에 bfs로 풀었다가 다시 푼 문제다. bfs로 풀면 방문한 곳을 재방문하지 않기 때문이다. 그래서 고민하다가 알고리즘 분류를 눌렀더니 다익스트라로 되어있어서 다익스트라로 다시 접근한 문제다.

 

다익스트라는 한 정점에서 다른 정점까지 최소비용으로 가는 방법을 찾는 알고리즘이다. (1, 1)에서 출발하고 상하좌우로 움직이는 도중에 도착한 좌표가 1인 경우 비용을 +1 증가시켜서 풀었다. 만약에 도착한 임의의 점까지의 비용보다 현재 가고자 하는 비용이 더 작다면 갱신한다. 갱신한 좌표는 큐에 다시 넣어준다. 이렇게 되면 최소비용으로 이동한 결과들만 결론적으로 큐에 담기고 방문여부에 상관없이 갔던 곳을 재탐색할 수 있다.

 

#include <iostream>
#include <queue>
#include <string>
#define MAX 101
using namespace std;

//좌표 정보
class Point {
public:
	int x, y;
	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
};

int N, M; //M줄, N칸
int mat[MAX][MAX]; //좌표 정보
int d[MAX][MAX]; //비용 정보
queue<Point> q; //다익스트라를 수행할 큐

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

string s; //숫자들을 입력받을 공간

void bfs(int x, int y) {
	q.push(Point(x, y));
	d[1][1] = 0; //출발점의 도달 가능한 비용은 0
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();

		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 (d[nx][ny] > d[x][y] + 1) { //현재 가고자 하는 비용에 1을 더한 값이 원래 (nx, ny)에 있던 값보다 작으면
						d[nx][ny] = d[x][y] + 1; //갱신
						q.push(Point(nx, ny)); //큐에 삽입
					}
				}
				else { //벽이 아니면
					if (d[nx][ny] > d[x][y]) { //현재 가고자 하는 비용이 원래 (nx, ny)에 있던 값보다 작으면
						d[nx][ny] = d[x][y]; //갱신
						q.push(Point(nx, ny)); //큐에 삽입
					}
				}
			}
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= M; i++) { //문제에서 M줄 N칸으로 줌
		cin >> s; //문자열로 받아서
		for (int j = 0; j < s.size(); j++) { //문자열 잘라서
			mat[i][j + 1] = s[j] - '0'; //1번지 부터 시작이니까 j + 1을 하여 좌표에 넣는다.
			d[i][j + 1] = 10000000; //우선 최소비용으로는 매우 큰 값을 넣는다.
		}
	}

	bfs(1, 1);

	cout << d[M][N];
}