BOJ) 1261 - 알고스팟

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

1261번: 알고스팟

시작점에서 가중치가 0 또는 1인 방들을 지나면서 도착점에 도달하는 최소비용을 구하는 문제입니다.

한 점에서 다른 점으로 가는 최소 비용을 구하는 다익스트라 알고리즘을 사용하여 최소 비용을 갱신하여 풀이했습니다.

---

C++ 소스 코드

#include <cstdio>
#include <queue>
#include <algorithm>
#define INF 98765
using namespace std;
int n,m;
int dist[101][101];
int a[101][101];
int dx[] = {1,0,0,-1}, dy[] = {0,-1,1,0};
int dijkstra(){
    priority_queue<pair<int, pair<int, int> > > pq; //비용, (x,y)
    dist[1][1] = 0;
    pq.push(make_pair(0,make_pair(1,1)));
    while(!pq.empty()){
        int nowd = -pq.top().first;
        int nowx = pq.top().second.first;
        int nowy = pq.top().second.second;
        pq.pop();
        for(int i=0;i<4;i++){
            int nx = nowx+dx[i], ny = nowy+dy[i];
            if (nx <1 || nx >m || ny <1 || ny<1 || ny >n) continue;
            if(dist[nx][ny]> dist[nowx][nowy]+a[nx][ny]){
                dist[nx][ny] = dist[nowx][nowy]+a[nx][ny];
                pq.push(make_pair(-dist[nx][ny],make_pair(nx,ny)));
            }
        }
    }
    return dist[m][n];
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%1d", &a[i][j]);
            dist[i][j] = INF;
        }
    }
    printf("%d",dijkstra());
    return 0;
}

---

Swift 소스 코드

import Foundation

func solution(){
    let dx = [1,0,0,-1]
    let dy = [0,-1,1,0]
    
    let input = readLine() ?? ""
    let nums = input.split{ $0 == " " }.map{ Int($0)! }
    let m = Int(nums[0])
    let n = Int(nums[1])
    
    var visit = [[Bool]](repeating: [Bool](repeating: false, count: m), count: n)
    var resultMap = [[Int]](repeating: Array(repeating: 0, count: m), count: n)
    
    
    var map = [[Int]](repeating: [Int](), count: n)
    for i in 0..<n {
        guard let strRow =  readLine() else { return }
        let arrRow = Array(strRow)
        let  row = arrRow.map {  Int(String($0))! }
        map[i] = row
    }
    
    var queueX:[Int] = [0]
    var queueY:[Int] = [0]
    
    while !queueX.isEmpty {
        let x = queueX[0]
        let y = queueY[0]
        queueX.removeFirst()
        queueY.removeFirst()
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            if nx < 0 || nx >= n || ny < 0 || ny >= m {
                continue
            }
            if visit[nx][ny] == true {
                if resultMap[nx][ny] > resultMap[x][y] + map[nx][ny] {
                    resultMap[nx][ny] = resultMap[x][y] + map[nx][ny]
                    queueX.append(nx)
                    queueY.append(ny)
                }
                continue
            }
            resultMap[nx][ny] = resultMap[x][y] + map[nx][ny]
            visit[nx][ny] = true
            queueX.append(nx)
            queueY.append(ny)
        }
    }
    print(resultMap[n-1][m-1])
}

solution()