[백준] 2931번 가스관 [C++]

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

2931번: 가스관

---

접근 방식

일단 모스크바에서 부터 가스관의 방향을 따라서 BFS를 통해서 탐색을 해준다.

탐색을 하다보면, 이어져 있지만 빈칸으로 뚫려있는 곳이 있게 되는데, 이 위치를 저장하고 어느 방향으로 탐색을 했는지도 저장해준다.

다시 자그레브에서 같은 방법으로 탐색을 해준다. 같은 지점에서 뚫려있게 되는데 여기서도 어느 방향으로 탐색했는지 저장해준다.

예를 들어 이러한 형태로 입력이 주어졌다고 가정해보자.

모스크바에서는 아래로 탐색을 하다보니 아래 방향이 비어있는 공간이 발견된다.

자그레브에서 가스관을 따라 탐색을 하다보니 오른쪽이 비어있는 공간이 발견될 것이다.

그렇다면, 비어있는 곳에 있어야 할 모양은

이 형태가 될 것이다.

이런 식으로 어느 방향이 비어있는지 2개를 알아낸 후에, 몇 가지 경우가 안되므로 if문을 통해서 해결을 하였다.

 

이런 식으로 할 때 살짝의 예외처리가 필요했는데

바로 위 그림에서 2,3 지점이 없어졌을 경우이다.

이 경우에도 위와 같이 자그레브에서 시작할 때 오른쪽이, 모스크바에서 시작할 때 아래쪽이 비어있지만, 들어가야 할 가스관의 모양은 달라진다.

따라서 비어있는 좌표에서, 네 방향을 탐색해 네 방향 모두 이어져 있다면

이 모양의 가스관을, 그 외에 경우에는 이어진 두 방향을 토대로 어떤 가스관이 들어갈지 알아내면 된다.

 

---

#include<iostream>
#include<queue>
using namespace std;
int n, m;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
char arr[26][26];
pair<int, int> mo;
pair<int, int> za;
pair<int, int> emptyArr;
int counter;
bool flag[26][26];
queue<pair<int, int>> q;
int moEmpty;
int zaEmpty;
void CheckRight(int x, int y, bool isMo, bool isCity) { //방향을 탐색하는 과정이다. isMo는
//모스크바에서 탐색을 할 경우, isCity는 모스크바,자그레브에서 탐색을 할 경우인데, 
//도시에서 이어진 수도관이 딱 한개밖에 없기 때문에 구분을 해줬다.
	y = y + 1;
	if (x > 0 && y > 0 && x <= n && y <= m && !flag[x][y]) {
		if (arr[x][y] == '.' && !isCity) {
			if (isMo)moEmpty = 0;
			else zaEmpty = 0;
			emptyArr = { x,y };
		}
		else if (arr[x][y] != '.') {
			flag[x][y] = true;
			q.push({ x,y });
		}
	}
}
void CheckLeft(int x, int y, bool isMo, bool isCity) {
	y = y - 1;
	if (x > 0 && y > 0 && x <= n && y <= m && !flag[x][y]) {
		if (arr[x][y] == '.' && !isCity) {
			if (isMo)moEmpty = 1;
			else zaEmpty = 1;
			emptyArr = { x,y };
		}
		else if (arr[x][y] != '.') {
			flag[x][y] = true;
			q.push({ x,y });
		}
	}
}
void CheckUp(int x, int y, bool isMo, bool isCity) {
	x = x - 1;
	if (x > 0 && y > 0 && x <= n && y <= m && !flag[x][y]) {
		if (arr[x][y] == '.' && !isCity) {
			if (isMo)moEmpty = 2;
			else zaEmpty = 2;
			emptyArr = { x,y };
		}
		else if (arr[x][y] != '.') {
			flag[x][y] = true;
			q.push({ x,y });
		}
	}
}
void CheckDown(int x, int y, bool isMo, bool isCity) {
	x = x + 1;
	if (x > 0 && y > 0 && x <= n && y <= m && !flag[x][y]) {
		if (arr[x][y] == '.' && !isCity) {
			if (isMo)moEmpty = 3;
			else zaEmpty = 3;
			emptyArr = { x,y };
		}
		else if (arr[x][y] != '.') {
			flag[x][y] = true;
			q.push({ x,y });
		}
	}
}
void CheckFromMo() {
	flag[mo.first][mo.second] = true;
	q.push({ mo.first,mo.second });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		int c = arr[x][y];
		q.pop();
		flag[x][y] = true;
		if (c == 'M') {
			CheckRight(x, y, true, true);
			CheckLeft(x, y, true, true);
			CheckDown(x, y, true, true);
			CheckUp(x, y, true, true);
		}
		else if (c == '+') {
			CheckRight(x, y, true, false);
			CheckLeft(x, y, true, false);
			CheckDown(x, y, true, false);
			CheckUp(x, y, true, false);
		}
		else if (c == '|') {
			CheckDown(x, y, true, false);
			CheckUp(x, y, true, false);
		}
		else if (c == '-') {
			CheckRight(x, y, true, false);
			CheckLeft(x, y, true, false);
		}
		else if (c == '1') {
			CheckRight(x, y, true, false);
			CheckDown(x, y, true, false);
		}
		else if (c == '2') {
			CheckRight(x, y, true, false);
			CheckUp(x, y, true, false);
		}
		else if (c == '3') {
			CheckLeft(x, y, true, false);
			CheckUp(x, y, true, false);
		}
		else if (c == '4') {
			CheckLeft(x, y, true, false);
			CheckDown(x, y, true, false);
		}
	}
}
void CheckFromZA() {
	flag[za.first][za.second] = true;
	q.push({ za.first,za.second });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		int c = arr[x][y];
		q.pop();
		flag[x][y] = true;
		if (c == 'Z') {
			CheckRight(x, y, false, true);
			CheckLeft(x, y, false, true);
			CheckDown(x, y, false, true);
			CheckUp(x, y, false, true);
		}
		else if (c == '+') {
			CheckRight(x, y, false, false);
			CheckLeft(x, y, false, false);
			CheckDown(x, y, false, false);
			CheckUp(x, y, false, false);
		}
		else if (c == '|') {
			CheckDown(x, y, false, false);
			CheckUp(x, y, false, false);
		}
		else if (c == '-') {
			CheckRight(x, y, false, false);
			CheckLeft(x, y, false, false);
		}
		else if (c == '1') {
			CheckRight(x, y, false, false);
			CheckDown(x, y, false, false);
		}
		else if (c == '2') {
			CheckRight(x, y, false, false);
			CheckUp(x, y, false, false);
		}
		else if (c == '3') {
			CheckLeft(x, y, false, false);
			CheckUp(x, y, false, false);
		}
		else if (c == '4') {
			CheckLeft(x, y, false, false);
			CheckDown(x, y, false, false);
		}
	}
}
void Solution() {
	cout << emptyArr.first << ' ' << emptyArr.second << ' ';
	int counter = 0;
	for (int i = 0; i < 4; i++) {
		int x2 = emptyArr.first + dx[i];
		int y2 = emptyArr.second + dy[i];
		if (x2 > 0 && y2 > 0 && x2 <= n && y2 <= m && arr[x2][y2] != '.' && arr[x2][y2] != 'M' && arr[x2][y2] != 'Z')
			counter++;
	}
	if (counter == 4) {
		cout << '+';
	}
	else {
		if (moEmpty == 0) {
			if (zaEmpty == 1) {
				cout << '-';
			}
			else if (zaEmpty == 2) {
				cout << 4;
			}
			else if (zaEmpty == 3) {
				cout << 3;
			}
		}
		else if (moEmpty == 1) {
			if (zaEmpty == 0) {
				cout << '-';
			}
			else if (zaEmpty == 2) {
				cout << 1;
			}
			else if (zaEmpty == 3) {
				cout << 2;
			}
		}
		else if (moEmpty == 2) {
			if (zaEmpty == 1) {
				cout << 1;
			}
			else if (zaEmpty == 0) {
				cout << 4;
			}
			else if (zaEmpty == 3) {
				cout << '|';
			}
		}
		else if (moEmpty == 3) {
			if (zaEmpty == 1) {
				cout << 2;
			}
			else if (zaEmpty == 2) {
				cout << '|';
			}
			else if (zaEmpty == 0) {
				cout << 3;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'M')mo = { i,j };
			else if (arr[i][j] == 'Z')za = { i,j };
		}
	CheckFromMo();
	CheckFromZA();
	Solution();
}

---

구현, 시뮬레이션 쪽은 코드가 지저분해지는 경우가 많은 것 같다...