[BOJ/백준][Gold4] 2151 : 거울 설치 (C++)

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

2151번: 거울 설치

 

[난이도] Gold4
[유형] BFS

[풀이]
BFS를 이용해 풀 수 있다.
각 문,거울에 번호를 준 뒤, 문,거울간에 인접행렬을 만들어서 풀수도 있지만
본인은 맵에서 한칸씩 움직이는 방식으로 풀었다.
메모제이션 배열은 visit[50][50][2]과 같이 선언해야 한다.
visit[y][x][0] -> 세로 방향에서 y,x에 도착한 경우.
visit[y][x][1] -> 가롱 방향에서 y,x에 도착한 경우.

두 방향으로 구분한 이유는 y,x에 거울을 설치할 수 있을 때,
세로 방향에서 왔을 때 거울을 설치하면 다음 방향으로 가로방향(좌,우)로 이동이 가능하고
가로 방향에서 왔으면 세로방향으로의 이동이 가능해지기 때문이다.
만약 visit[50][50]으로만 해놓고 풀면 방향전환을 할 수 없는 경우가 생기게 된다.

큐에는 {y,x,d,k}를 넣어준다. d는 현재 움직이고 있는 방향이고, k는 현재까지 사용한 거울 개수이다.
만약 '.'인 칸이면 그냥 d방향으로만 전진하고 거울설치가 가능한 '!' 칸이면 좌우로 방향이 바뀌는 경우도
k+1을 해주고 추가로 큐에 넣어주면 된다.

 

 

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
int N,visit[50][50][2],sy=-1,sx,ey,ex;
char map[50][50];
struct P{
    int y,x,d,k;
};
int main(){ 
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='#') {
                if(sy==-1)sy=i,sx=j;
                else ey=i,ex=j;
            }
        }
    }
    memset(visit,-1,sizeof(visit));
    queue<P> q;
    for(int i=0;i<4;i++) {
        q.push({sy,sx,i,0});
        visit[sy][sx][i%2]=0;
    }
    while(!q.empty()){

        P f = q.front(); q.pop();
        int ny = f.y+dy[f.d], nx = f.x+dx[f.d];
        if(ny < 0 || nx < 0 || ny >= N || nx >= N || map[ny][nx]=='*') continue;
        
        if(visit[ny][nx][f.d%2]==-1 || visit[ny][nx][f.d%2] > f.k) {
            visit[ny][nx][f.d%2] = f.k;
            q.push({ny,nx,f.d,f.k});
        }        
        if(map[ny][nx]=='!'){
            if(visit[ny][nx][(f.d+1)%2]==-1 || visit[ny][nx][(f.d+1)%2] > f.k+1) {
                visit[ny][nx][(f.d+1)%2] = f.k+1;
                q.push({ny,nx,(f.d+1)%2,f.k+1});
                q.push({ny,nx,2+(f.d+1)%2,f.k+1});
            }            
        }
    }
    int ans = 9e8;
    if(visit[ey][ex][1]!=-1) ans = min(ans,visit[ey][ex][1]);
    if(visit[ey][ex][0]!=-1) ans = min(ans,visit[ey][ex][0]);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2151.cpp