[백준 2151]거울설치

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

1)문제분류

  -BFS

  -다익스트라

2)해결방법

  - 거울설치는 45도 이다.그러므로 거울이 /와 \  (걍 이해하기쉽게 거울을 표현한 문자) 두가지로 꺾인다고 생각하고 문제를 푼다.

  예) -> 오른쪽방향으로오는경우 / 을 만나면 ↑

                                           \을 만나면  ↓ 

        오른쪽방향,왼쪽방향으로 갈때 거울반사에 의해 꺾이는 방향 동일하다.

        위쪽방향,아래쪽방향으로 갈때  거울반사에 의해 꺾이는 방향 동일하다.

 - 대신 거울이 설치 될수있는 위치가 ' ! '라고 표현한것이므로  거울 설치 안하는 경우도 생각해줘야한다.

    그냥 통과하는 경우도 고려해서  거울 설치 최소값을 구해야한다.!

 

 -현재 위치에서 바라보는 방향이 같다는 가정하에 ,이제것 설치한 거울 수가 적으면 큐에 넣어준다.

  바라보고있는 방향에 따라 거울반사가 달라지기때문에  chk배열은 3차원으로 관리하여 비교해서 큐에 삽입해야한다...  chk [x][y][방향]  

  

만약, 2차원으로 해버린다면[x][y], 방향이 다르고 거울설치갯수가 같은게 있다고 하자.

[x][y] 이 지점에 오른방향과 아래방향으로 가는 데이터가 지나가야한다고 가정할때, 

오른쪽으로 방향으로 가는 데이터가 먼저 chk[x][]를 선점해버리면 

아래방향으로 가야할 데이터는 chk[][]를 못가게된다..

 그렇기때문에 3차원으로 해서 chk방향을 구분해야한다

//주의할점 (내가 실수 했던 부분 )

//Search()에서 문의 위치 발견시 바로 리턴을시켜서 함수를 종료시켰는데

//먼저 문을 발견했다고해서 거울의 최소값이 될 수 없음을 주의하자.

//먼저 도착한건 최단거리 일뿐, 거울의 개수가 최소값이라는 보장이 없기 때문에.

//멀리 돌아서 오더라도 거울의 개수가 적은걸 뽑아야하는게 이 문제의 핵심이다.

#include <iostream>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

char map[52][52];

int chk[52][52][5]; //최소값 넣을꺼임 

int n, sx, sy, ex, ey,ok;

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

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

typedef struct Data

{

int x, y, dir, cnt;

}Data;

bool range(int rx, int ry)

{

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

else return true;

}

void Serach(int sx,int sy,int d,int c)

{

queue<Data>pq;

pq.push({ sx,sy,d,c });

while (!pq.empty())

{

Data output = pq.front();

pq.pop();

int cx = output.x + xrr[output.dir];

int cy = output.y + yrr[output.dir];

if (range(output.x, output.y) == false || map[cx][cy] == '*')continue;

if (map[cx][cy] == '!')

{

if (output.dir==0||output.dir==3)//거울 반사

{

if (chk[cx][cy][1] > output.cnt + 1)

{

chk[cx][cy][1] = output.cnt + 1;

pq.push({ cx,cy,1,output.cnt + 1 });

}

if (chk[cx][cy][2] > output.cnt + 1)

{

chk[cx][cy][2] = output.cnt + 1;

pq.push({ cx,cy,2,output.cnt + 1 });

}

}

if (output.dir == 1 || output.dir == 2)//거울 반사

{

if (chk[cx][cy][0] > output.cnt + 1)

{

chk[cx][cy][0] = output.cnt + 1;

pq.push({ cx,cy,0,output.cnt + 1 });

}

if (chk[cx][cy][3] > output.cnt + 1)

{

chk[cx][cy][3] = output.cnt + 1;

pq.push({ cx,cy,3,output.cnt + 1 });

}

}

}

if (chk[cx][cy][output.dir] > output.cnt)//그냥 지나칠경우 

{

chk[cx][cy][output.dir] = output.cnt;

pq.push({ cx,cy,output.dir,output.cnt });

}

}

}

int main()

{

cin >> n;

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

{

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

{

cin >> map[i][j];

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

  chk[i][j][k] = 9898989;

if (map[i][j] == '#')

{

map[i][j] = '.';

if (ok == 0)

{

sx = i;

sy = j;

ok = 1;

}

else

{

ex = i;

ey = j;

}

}

}

}

int ans = 98989898;

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

{

Serach(sx,sy,i,0 );

}

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

{

ans = min(chk[ex][ey][i], ans);

}

cout << ans << endl;

}