[백준 2665] 미로만들기

www.acmicpc.net/problem/2665

2665번: 미로만들기

최소거리기 때문에 bfs나 다익스트라 둘다 사용가능하다.

다익스트라를 연습하기 위해! 다익스트라로 풀었다.

 

검은색은 비용을 1 하얀색은 비용을 0으로 하여 arr[n-1][n-1]까지 도달하는 최소 비용을 계산한다.

처음 모든 거리는 inf로 초기화한후 조건을 만족하면 거리를 업데이트한다. 

최소 비용을 구해야 하기 때문에 pop한 cur가 목적지에 해당한다고 break하지 않고 끝까지 진행한다.

#include <stdio.h>
#include <queue>
#define INF 1e9

using namespace std;
int arr[50][50];
int dis[50][50];
int n;

struct s
{
  int row, col, cost;
};

struct cmp
{
  bool operator()(const s &l, const s &r)
  {
    if (l.cost == r.cost)
    {
      if (l.row == r.row)
      {
        return l.col < r.col;
      }
      return l.row < r.row;
    }
    return l.cost > r.cost;
  }
};

priority_queue<s, vector<s>, cmp> pq;

void Print()
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      printf("%d ", dis[i][j]);
    }
    printf("\n");
  }
  printf("\n");
}

int Dijkstra()
{
  int dr[4] = {0, 0, -1, 1};
  int dc[4] = {1, -1, 0, 0};
  pq.push({0, 0, 0});
  dis[0][0] = 0;

  while (!pq.empty())
  {
    s cur = pq.top();
    pq.pop();

    for (int i = 0; i < 4; i++)
    {
      int nr = cur.row + dr[i];
      int nc = cur.col + dc[i];

      if (nr < 0 || nc < 0 || nr > n - 1 || nc > n - 1)
      {
        continue;
      }

      if (dis[nr][nc] > cur.cost + arr[cur.row][cur.col])
      {
        dis[nr][nc] = cur.cost + arr[cur.row][cur.col];
        pq.push({nr, nc, dis[nr][nc]});
      }
    }
  }

  return dis[n - 1][n - 1];
}
int main(void)
{
  scanf("%d", &n);

  char tmp[51];
  for (int i = 0; i < n; i++)
  {
    scanf("%s", tmp);

    for (int j = 0; j < n; j++)
    {
      arr[i][j] = tmp[j] == '1' ? 0 : 1;
      dis[i][j] = INF;
    }
  }

  int res = Dijkstra();
  printf("%d\n", res);

  return 0;
}