[ BOJ / C++ ] 21922번 : 학부 연구생 민상

[ BOJ ] 21922번 : 학부 연구생 민상

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

21922번: 학부 연구생 민상

---

[  문제  ]

학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.

연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.

민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.

연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.

연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.

연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.

민상이가 원하는 자리는 몇 개 있는지 계산해주자.

[  입력  ]

첫 번째 줄에는 연구실의 크기가 세로 N(1 ≤ N ≤ 2,000), 가로 M(1 ≤ M ≤ 2,000) 순으로 주어진다.

두 번째 줄부터 N+1줄까지 연구실 내부 구조 정보를 알려주는 값 M개가 주어진다.

 1,2,3,4는 위에서 설명한 물건의 종류이다.

 9는 에어컨을 의미하고, 0은 빈 공간을 의미한다.

에어컨은 0개 이상 50개 이하가 들어온다.

[  출력  ]

민상이가 원하는 자리의 개수를 출력한다.

---

[  문제 접근 및 풀이  ]

1. Queue의 인자로는 구조체인 x좌표, y좌표, 바람의 방향을 넣었다.

2. 에어컨을 받았을 때 4방향을 Queue에 넣는다.

3. 같은 곳에 있어도 방향이 다르면 가는 곳이 다르기에 vis[4][ ][ ] 3차원 배열로

방향마다 방문 표시를 해줬다.

4. 또한 민상이가 앉을 자리는 다른 배열로 cnt[ ][ ] 2차원 배열로 받아주어 따로 계산했다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int N,M,sit,board[2001][2001];
bool cnt[2001][2001],vis[4][2001][2001];//cnt[][]는 갯수를 세기 위함, vis[][][]는 방향마다 방문처리
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; //아래,오른쪽,위,왼쪽
typedef struct wind{
    int x,y,dir;
}W;
void input();
void solve();
int dir_wind(int x,int y,int dir);
queue<W> Q;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	input();
	solve();
} 
void input(){
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin >> board[i][j];
            if(board[i][j]==9){
                cnt[i][j]=true;
                for(int dir=0;dir<4;dir++) vis[dir][i][j]=true,Q.push({i,j,dir});
            }
        }
    }
}
void solve(){
    while(!Q.empty()){
        auto cur=Q.front(); Q.pop();
        int nx=cur.x+dx[cur.dir],ny=cur.y+dy[cur.dir],dir=cur.dir;
        if(nx<0 || ny<0 || nx>= N|| ny>=M) continue;
        if(vis[dir][nx][ny]) continue;
        vis[dir][nx][ny]=true;
        cnt[nx][ny]=true;
        dir=dir_wind(nx,ny,dir);
        Q.push({nx,ny,dir});
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++) {
            if(cnt[i][j]) sit++;
        }
    }
    cout<< sit;
}
int dir_wind(int x,int y,int dir){
    if((board[x][y]==1 &&(dir==1 || dir==3))|| (board[x][y]==2&& (dir==2 || dir==0))){
        return (dir+2)%4;
    }
    else if(board[x][y]==3){
        if(dir==0) return 3; //밑에서 왼쪽으로 
        else if(dir==1)return 2; //오른쪽에서 위로
        else if(dir==2) return 1; //위에서 오른쪽
        else return 0; //왼쪽에서 밑으로
    }
    else if(board[x][y]==4){
        if(dir==0) return 1; //밑에서 오른쪽으로
        else if(dir==1)return 0; //오른쪽에서 밑로
        else if(dir==2) return 3; //위에서 왼쪽
        else return 2; //왼쪽에서 위으로
    }
    return dir;
}

---