[백준] 2665 미로만들기, python, C++

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

2665번: 미로만들기

우선순위큐를 사용해서 해결할수 있었다.

# import sys; input = sys.stdin.readline
from heapq import heappop, heappush

def dijkstra(N):
    visit = [[False for _ in range(N)] for _ in range(N)]
    h = [(0, 0, 0)]  # cost, r, c

    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    while h:
        cost, r, c = heappop(h)
        if r == N - 1 and c == N - 1:
            return cost
        if visit[r][c]:
            continue
        visit[r][c] = True
        for i in range(4):
            dr, dc = r + d[i][0], c + d[i][1]
            if dr < 0 or dr >= N or dc < 0 or dc >= N:
                continue

            if _map[dr][dc] == '1':
                heappush(h, (cost, dr, dc))
            else:
                heappush(h, (cost + 1, dr, dc))

    # 혹시라도 에러가 발생하는 경우, -1 반환. 못찾는 경우는 없음
    return -1

N = int(input())
_map = [input().rstrip() for _ in range(N)]
print(dijkstra(N))

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

#define p pair<int, int>
#define pp pair<int, p>

string map[50];

int dijkstra(int N) {
	int cost, r, c, i, dr, dc;
	vector<vector<bool>> visit(N, vector<bool>(N, false));

	priority_queue<pp> h;
	int d[8] = { 0, 1, 1, 0, -1, 0, 0, -1 };
	h.push(pp(0, p(0, 0)));
	while (!h.empty()) {
		pp cur = h.top(); h.pop();
		cost = -cur.first;
		r = cur.second.first;
		c = cur.second.second;
		if (r == N - 1 && c == N - 1)
			return cost;
		if (visit[r][c])
			continue;
		visit[r][c] = true;
		for (i = 0; i < 4; i++)
		{
			dr = r + d[2 * i];
			dc = c + d[2 * i + 1];
			if (dr < 0 || dr >= N || dc < 0 || dc >= N)
				continue;

			if (map[dr][dc] == '1') {
				h.push(pp(-cost, p(dr, dc)));
			}
			else {
				h.push(pp(-(cost + 1), p(dr, dc)));
			}
		}
	}
	return -1;
}

int main() {
	int N, i;
	cin >> N;
	for (i = 0; i < N; i++)
		cin >> map[i];
	cout << dijkstra(N);
	return 0;
}