문제

boj2665_1 boj2665_2

다익스트라로 모든 노드를 다 방문하되, 흰 방에는 weight 0을, 검은 방에는 weight로 1을 준다. 그러면 흰 방을 우선으로 방문하면서 해당 노드까지 이동하면서 거쳐온 검은 방의 개수를 구할 수 있다!

재밌게 풀었고 풀면서 다익스트라 복습도 해서 좋았다.

다익스트라 알고리즘

알고리즘 수업 내용과 구현

  • 그래프의 한 vertex(모든 edge가 0 또는 양수 weight를 가지는 )에서 모든 vertex까지의 최단 거리를 각각 구하는 알고리즘
  • 최단 거리를 노드의 개수번 만큼 구하는 것보다 빠르다.
  • edge의 방향성 유무는 상관 없음
  • PQ나 heap을 사용하면 O((V+E)logV)의 시간 복잡도를 가짐
    • 각 노드를 방문할 때마다 아직 방문하지 않은 노드로부터 현재까지 계산된 최단거리를 찾고 O(VlogV)
    • 각 노드마다 이웃 노드의 최단거리를 갱신 O(ElogV)하기 때문
      • 모든 edge를 확인해 O(E) 매번 PQ/heap에서 최단거리를 갱신 O(logV)해주기 때문. 이는 모든 노드를 방문해 확인하는 것 O(logN)보다 빠르다.

알고리즘

  1. 변수 선언 및 초기화
    • 노드 간 weight를 저장할 자료구조(adjacency graph/matrix 등)에 값 입력
    • 시작점으로부터의 최단거리를 저장할 배열 dist[N]의 모든 원소를 INF로 초기화
    • 각 노드의 방문 여부를 저장할 배열 visited[N]를 false로 초기화
    • 노드들의 최단거리를 저장할 PQ/heap 선언
  2. 시작 노드를 PQ에 push
  3. PQ(값이 작은 순서대로 꺼냄)가 빌 때까지 3~9번 과정 반복
  4. PQ의 top을 pop해 현재 보고 있는 노드 A를 기준으로
  5. A의 모든 이웃 노드 B에 대하여 6~9번 수행
  6. 시작 노드로부터 A까지의 거리인 dist[A] + A에서 B까지의 거리(weight) weight[A][B], 즉 시작점에서부터 A를 거쳐 B로 가는 길이 dist[A] + weight[A][B]와, 시작점에서부터 바로 B까지 가는 길이 dist[B]값 비교
  7. dist[A] + weight[A][B] < dist[B]라면 dist[B]의 값을 dist[A] + weight[A][B]로 갱신
  8. A를 방문했다고 표시하고 (visited[A] = true)
  9. B를 PQ<거리, 노드이름>에 push
  10. 도착 노드를 방문하거나 혹은 도착노드를 방문하지 못했지만 PQ가 빈 경우(도착점까지 갈 수 없는 경우) 알고리즘 종료

다익스트라로 푼 문제들

구현


#include <iostream>
#include <cstring> // memset
#include <string>
#include <vector>
#include <utility> // pair
#include <queue> // pq
#define MAX 51
#define INF 0x7FFFFFFF
using namespace std;

int dist[MAX][MAX]; // current shortest distance from (1, 1)
bool isWhite[MAX][MAX]; // white: weight = 1, black: weight = 0
bool visited[MAX][MAX];

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

	int N, i, j, nowR, nowC;
	string str;
	priority_queue< pair< int, pair<int, int> >, vector< pair< int, pair<int, int> > >, greater< pair< int, pair<int, int> > > > pq; // (dist, (row, col))
	memset(isWhite, true, sizeof(isWhite));
	memset(visited, false, sizeof(visited));

	cin >> N;
	for (i = 1; i <= N; i++) {
		cin >> str;
		for (j = 1; j <= N; j++) {
			dist[i][j] = INF;
			if (str[j - 1] == '0') isWhite[i][j] = false;
		}
	}

	nowR = 1, nowC = 1;
	dist[nowR][nowC] = 0;
	pq.push(make_pair(0, make_pair(nowR, nowC)));

	while (!pq.empty()) {
		int tmpDist = pq.top().first;
		int nowR = pq.top().second.first;
		int nowC = pq.top().second.second;
		//		cout << "now: (" << nowR << ", " << nowC << ") with distance " << tmpDist << endl;
		pq.pop();
		if (!visited[nowR][nowC]) {
			visited[nowR][nowC] = true;

			if (nowR - 1 >= 1) { // UP
				if (tmpDist + (isWhite[nowR - 1][nowC] ? 0 : 1) < dist[nowR - 1][nowC]) {
					dist[nowR - 1][nowC] = tmpDist + (isWhite[nowR - 1][nowC] ? 0 : 1);
				}
				if (!visited[nowR - 1][nowC]) pq.push(make_pair(dist[nowR - 1][nowC], make_pair(nowR - 1, nowC)));
				//				cout << "next: (" << nowR - 1 << ", " << nowC << ") with distance " << dist[nowR - 1][nowC] << endl;
			}

			if (nowR + 1 <= N) { // DOWN
				if (tmpDist + (isWhite[nowR + 1][nowC] ? 0 : 1) < dist[nowR + 1][nowC]) {
					dist[nowR + 1][nowC] = tmpDist + (isWhite[nowR + 1][nowC] ? 0 : 1);
				}
				if (!visited[nowR + 1][nowC]) pq.push(make_pair(dist[nowR + 1][nowC], make_pair(nowR + 1, nowC)));
				//				cout << "next: (" << nowR + 1 << ", " << nowC << ") with distance " << dist[nowR + 1][nowC] << endl;
			}

			if (nowC - 1 >= 1) { // LEFT
				if (tmpDist + (isWhite[nowR][nowC - 1] ? 0 : 1) < dist[nowR][nowC - 1]) {
					dist[nowR][nowC - 1] = tmpDist + (isWhite[nowR][nowC - 1] ? 0 : 1);
				}
				if (!visited[nowR][nowC - 1]) pq.push(make_pair(dist[nowR][nowC - 1], make_pair(nowR, nowC - 1)));
				//				cout << "next: (" << nowR << ", " << nowC - 1 << ") with distance " << dist[nowR][nowC - 1] << endl;
			}

			if (nowC + 1 <= N) { // RIGHT
				if (tmpDist + (isWhite[nowR][nowC + 1] ? 0 : 1) < dist[nowR][nowC + 1]) {
					dist[nowR][nowC + 1] = tmpDist + (isWhite[nowR][nowC + 1] ? 0 : 1);
				}
				if (!visited[nowR][nowC + 1]) pq.push(make_pair(dist[nowR][nowC + 1], make_pair(nowR, nowC + 1)));
				//				cout << "next: (" << nowR << ", " << nowC + 1 << ") with distance " << dist[nowR][nowC + 1] << endl;
			}
		}
	}

	cout << dist[N][N] << endl;
	return 0;
}