프로그래머스 - (PCCP 모의고사) 보물 지도 c++

https://school.programmers.co.kr/learn/courses/15009/lessons/121690

프로그래머스

bfs를 약간 변형한 문제로, 이동시 신비로운 신발을 사용하여 두칸을 한번에 이동할 수 있다.

방문여부를 확인할 배열을 2차원 배열이 아닌 3차원 배열을 사용하여 방문여부를 확인한다.

visited[1001][1001][2]

ex)

(2,3)을 지날 때 신비로운 신발을 사용 했으면 visited[2][3][1] = true;

(2,3)을 지날 때 신비로운 신발을 사용 안했으면 visited[2][3][0] = true;

 

bfs순회를 하면서 각 점을 지날 때 마다 '신비로운 신발' 사용 여부에 따른 분기점이 2개씩 생긴다.

그렇기 때문에 bfs순회시 신발 사용 여부에 따라 현재 위치와 신발 사용 여부를 queue에 적절히 추가할 필요가 있다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int board[1001][1001];
bool visited[1001][1001][2];

int solution(int n, int m, vector<vector<int>> hole) {
  int answer = -1;
  for (auto a : hole) {
    int x = a[0];
    int y = a[1];
    board[x][y] = 1;
  }
  queue<vector<int>> Q;
  Q.push({1, 1, 0, 0});
  while (!Q.empty()) {
    int x, y, used, dist;
    auto cur = Q.front();
    Q.pop();
    x = cur[0];
    y = cur[1];
    used = cur[2];
    dist = cur[3];
    if (x == n && y == m) {
      answer = dist;
      break;
    }
    if (x < 1 || x > n || y < 1 || y > m || visited[x][y][used] || board[x][y])
      continue;
    visited[x][y][used] = true;
    for (int i = 0; i < 4; i++) {
      Q.push({x + dx[i], y + dy[i], used, dist + 1});
      if (used == 0) {
        Q.push({x + dx[i] * 2, y + dy[i] * 2, 1, dist + 1});
      }
    }
  }
  return answer;
}