[백준 21922번] 학부 연구생 민상

[백준 21922번] 학부 연구생 민상

www.acmicpc.net/problem/21922

21922번: 학부 연구생 민상

 

 

 문제

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

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

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

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

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

물건 종류	물건 모양	바람의 이동 방향
물건 1
물건 2
물건 3
물건 4

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

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

 

 입력

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

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

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

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

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

 

 출력

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

 

 

 풀이

#include <iostream>
#include <queue>
using namespace std;
int N, M;
int arr[2000][2000];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
bool check[2000][2000][4];

int cd(int item, int d){
	if(item == 0) return d;
	else if(item == 1){
		if(d == 0) return 2;
		else if(d == 2) return 0;
		else return d;
	}
	
	else if(item == 2){
		if(d == 1) return 3;
		else if(d == 3) return 1;
		else return d;
	}
	
	else if(item == 3){
		if(d == 0) return 3;
		else if(d == 1) return 2;
		else if(d == 2) return 1;
		else return 0;
	}
	
	else if(item == 4){
		if(d == 0) return 1;
		else if(d == 1) return 0;
		else if(d == 2) return 3;
		else return 2;
	}
	else{
		if(d == 0) return 2;
		else if(d == 1) return 3;
		else if(d == 2) return 0;
		else return 1;
	}
}

void ff(int a, int b){
	queue<pair<pair<int, int>, int>> q;
	for(int i=0;i<4;i++){
		q.push(make_pair(make_pair(a, b), i));
		check[a][b][i] = true;
	}
	
	while(!q.empty()){
		int a = q.front().first.first;
		int b = q.front().first.second;
		int d = q.front().second;
		q.pop();
		
		
		int aa = a + dx[d];
		int bb = b + dy[d];
		if(aa < 0 || aa >= N || bb < 0 || bb >= M) continue;
			
		
		int dd = cd(arr[aa][bb], d);
		if(!check[aa][bb][dd]){
			check[aa][bb][dd] = true;
			q.push(make_pair(make_pair(aa, bb), dd));
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N >> M;
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			cin >> arr[i][j];
		}
	}
	int s = 0;
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			if(arr[i][j] == 9){
				ff(i, j);
			}
		}
	}
	
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			for(int k=0;k<4;k++){
				if(check[i][j][k]){
					s++;
					break;
				}
			}
		}
	}cout << s << '\n';

	return 0;
}

 일반적인 BFS에 방향전환과 방문처리만 조금 어려웠던 문제였다. 방향전환은 그냥 조건에 맞게 일일히 if문으로 변경해주었다. 방문처리가 문제였는데, 다시 돌아오다가 더 길게 뻗을 수 있기 때문에 한 바람에 대해 그냥 방문처리를 하면 안되고, 방향 요소를 포함하여 방문처리를 해야한다. 같은 지점에서 같은 방향일 때 경로가 같아서 더 탐색을 하지않아도 되는 문제도 해결 가능해진다. 설명이 약간 어려운데... 방문처리배열 check[2000][2000][4]로 3차원으로 만들어서 해결했다. BFS 마스터했다고 생각했는데 좀 더 알게 해준 좋은 문제였다.