[백준 16933]벽 부수고 이동하기 3

문제: https://www.acmicpc.net/problem/16933

1)문제분류

-다익스트라

-BFS

2)문제해결 

-벽부수고 이동하기 1,2 를 풀고 이 문제 풀기를 추천

- chk[x][y][현재까지 부순 벽 개수] =현재까지의 최단 경로비용을 저장(다익스트라)하며 큐를 돌린다.

- chk를 3차원으로 하는 이유는, 예를 들어 chk[x][y]로만 해버리면 만약 k가 3이라고 했을때, 

  chk[x][y]에 오는 데이터가 순서대로 [벽을 부신 횟수가 3,경로비용2],[벽을부신횟수가 2,경로비용2]라고 하면

  chk[x][y]에 먼저 [벽을 부신 횟수가 3,경로비용2] 을 받아 chk[x][y]=2를 저장한다.

  그 다음에 [벽을부신횟수가 2,경로비용2] 의 데이터가 왔을때, 벽을 부신 횟수가 2여서 다음 턴에서 한번 더 벽을 부실수 있는 기회가 있음    에도  불구하고, 현재 들어있는 chk[x][y]의 값보다  지금 들어오는 경로비용이 작지 않기때문에 검사를 하지 못하게된다.

  그래서 ,chk[][][벽을 부신 횟수],chk를 3차로 둬서 다익스트라로 문제를 풀어야한당.

-경로의 길이에 따라 낮과 밤이 변한다.

- 현재 내 코드에서는, Data에 있는 cnt가 짝수이면 낮이고, 홀수이면 밤

- 머무르는 시점은, 벽을 부술수 있는데 밤이라서 못부술때 낮이될때까지 머물러야하기에 경로길이+1 해서 다음턴에서 검사

 

#include<iostream>

#include<queue>

#include<algorithm>

using namespace std;

char map[1002][1002];

int chk[1002][1002][12];

int n, m,k;

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

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

typedef struct Data

{

int x, y, cnt, flag;

}Data;

bool range(int rx, int ry)

{

if (rx<0 || ry<0 || rx>n - 1 || ry>m - 1)return false;

else return true;

}

void bfs()

{

queue<Data>pq;

pq.push({ 0,0,0,0 });

chk[0][0][0] = 0;

while (!pq.empty())

{

Data output = pq.front();

pq.pop();

   

if (output.x == n - 1 && output.y == m - 1)

{

cout << output.cnt+1<< endl;

return;

}

for (int i = 0; i < 4; i++)

{

Data input;

input.x = output.x + xrr[i];

input.y = output.y + yrr[i];

input.flag = output.flag;

input.cnt = output.cnt;

if (range(input.x, input.y))

{

if (map[input.x][input.y] == '0')

{

if (input.cnt + 1 < chk[input.x][input.y][input.flag])

{

chk[input.x][input.y][input.flag] = input.cnt + 1;

pq.push({ input.x,input.y,input.cnt + 1,input.flag });

}

}

else

{

if (input.flag < k) //벽 격파할 횟수 남았니?

{

if (input.cnt % 2 == 0) //낮에 벽 부수기 가능 

{

if (input.cnt + 1 < chk[input.x][input.y][input.flag + 1])

{

pq.push({ input.x,input.y,input.cnt + 1,input.flag + 1 });

chk[input.x][input.y][input.flag + 1] = input.cnt + 1;

}

}

else //밤이면 머무르기

{

pq.push({ output.x,output.y,input.cnt + 1,input.flag });

}

}

}

}

}

}

cout << -1 << endl;

}

int main()

{

cin >> n >> m>>k;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

cin >> map[i][j];

for (int a = 0; a < 11;a++)

   chk[i][j][a] = 987654321;

}

}

bfs();

}