[백준] 로마 카톨릭 미사 (9518번)

문제

로마 카톨릭 미사에서 가장 멋진 부분은 사람들이 서로 악수를 하면서 "평화가 함께하기를" 이라고 말하는 평화 의식이다.

성당에는 R개의 벤치가 한 행에 하나씩 있고, 각 벤치에는 총 S명이 앉을 수 있다. 성당의 좌석 배치는 크기가 R × S인 행렬로 나타낼 수 있고, 행렬의 각 원소는 사람이 있는지 없는지로 나타낼 수 있다. 모든 사람은 자신의 이웃과 악수를 한다고 가정한다. 이웃은 사람이 있는 칸과 인접한 칸 여덟개이다. (칸이 존재하지 않을 수도 있다)

상근이는 오늘도 늦잠을 자 미사에 늦었고, 가장 좋아하는 평화 의식 시간을 참여하기 위해 성당 입구까지 달려왔다. 상근이는 최대한 많은 사람과 악수를 할 수 있는 자리에 앉으려고 한다. 만약, 남은 자리가 없는 경우에는 상근이는 저녁 미사에 다시 참가하려고 한다. 또, 상근이보다 지각하는 사람은 없다.

상근이가 들어가기 바로 전 성당에 앉아있는 사람의 배치가 주어진다. 평화 의식이 진행되는 동안 총 몇 번의 악수가 행해지는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 S가 주어진다. (1 ≤ R, S ≤ 50)

다음 R개 줄에는 S개의 문자가 주어진다. 이 R × S 개의 문자는 성당에 자리 배치를 나타낸다. '.'은 빈 자리, 'o'는 사람이 앉아있는 자리이다.

출력

평화 의식에서 총 몇 번의 악수가 행해지는지 출력한다.

예제 입력 1 복사

2 3 ..o o..

예제 출력 1 복사

2

---

문제 설명과 예제가 애매해서 실수할 여지가 있는 문제다.

문제는 상근이가 추가되었을 때의 악수 횟수가 아닌, 상근이를 포함해서 총 몇번의 악수가 이루어지는지를 묻고 있다.

따라서 브루트포스로 상근이를 모든 빈 좌석에 앉혀서 총 몇번의 악수가 이뤄지는지를 계산해야 한다. 

 

그런데 상근이를 어디에 앉히던, 기존에 있던 사람들끼리의 악수 횟수는 변하지 않기 때문에, 기존의 사람들의 총 악수횟수를 구한 후, 상근이의 최대 악수 횟수를 더하면 답을 구할 수 있다.

 

기존 사람들의 악수 횟수는 bfs를 이용해서 계산했다. 주의할점은 2차원 배열로 악수 여부를 기록하지 말고, 4차원 배열로 (x1,y1) - (x2,y2)의 악수 여부를 기록해야 한다. 나는 visit[][] 2차원 배열로 큐에 넣어서 조사했는지를 기록하고, 

hand[][][][] 4차원 배열로 두 사람의 악수 여부를 기록했다. 이런 방식으로 모든 사람의 악수 여부를 기록한 후, 각 빈자리에 상근이를 앉히며, 8가지 주위 방향에 사람이 몇 명 있는지를 계산하면 최대 악수 횟수를 구할 수 있다. 

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%A1%9C%EB%A7%88%20%EC%B9%B4%ED%86%A8%EB%A6%AD%20%EB%AF%B8%EC%82%AC%20(9518%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
using namespace std;

int R, S, res;
int hand[51][51][51][51]; // (a,b) - (x,y)의 악수 여부 기록
int visit[51][51]; // (a,b)를 조사했는가. 조사 여부와 악수 여부는 다르다.
int p[51][51]; // 좌석 기록
int dx[8] = { -1,0,1,1,1,0,-1,-1 }; // 8가지 방향
int dy[8] = { 1,1,1,0,-1,-1,-1,0 };

void bfs(int a, int b)
{
	queue<pair<int, int>> q;
	q.push({ a,b });
	visit[a][b] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		visit[x][y] = 1; 

		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || ny< 1 || nx > R || ny > S) continue;
			if (p[nx][ny] == 0) continue; //빈 좌석이면 건너뜀
			if (hand[x][y][nx][ny] == 1) continue; //악수 했으면 건너뜀
			q.push({ nx,ny });
			hand[x][y][nx][ny] = hand[nx][ny][x][y] = 1;
			res++; //악수 횟수 추가
		}
	}
}

int main()
{
	cin >> R >> S;
	string str;
	for (int i = 1; i <= R; i++) {
		cin >> str;
		for (int j = 1; j <= S; j++) {
			if (str[j - 1] == '.') p[i][j] = 0;
			else p[i][j] = 1;
		}
	}

	for (int i = 1; i <= R; i++) 
		for (int j = 1; j <= S; j++) 
			if (visit[i][j] == 0 && p[i][j] == 1) 
				bfs(i, j); // (i, j) 조사. 상근이 없이 최대 몇 번 악수하는지 조사

	int maxNum = 0; // 상근이가 악수할 최대 회수 기록
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= S; j++) {
			if (p[i][j] == 1) continue; // 빈좌석만 앉아야 한다.
			int cur = 0;
			for (int k = 0; k < 8; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				if (nx<1 || ny<1 || nx>R || ny>S) continue;
				if (p[nx][ny] == 1) cur++; // 악수 회수 추가
			}
			maxNum = max(maxNum, cur);
		}
	}

	cout << res + maxNum; // 상근이 없이 악수하는 횟수 + 상근이가 추가 됐을 때 추가 악수 횟수
}