C++ / 21736 / 헌내기는 친구가 필요해 ( 너비 우선 탐색 )

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

문제 요약

2020년에 입학한 헌내기 도연이가 있습니다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었습니다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶습니다.

도연이가 다니는 대학의 캠퍼스는 N×M$N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것입니다. 예를 들어, 도연이가 (x$x$, y$y$)에 있다면 이동할 수 있는 곳은 (x+1$x+1$, y$y$), (x$x$, y+1$y+1$), (x−1$x-1$, y$y$), (x$x$, y−1$y-1$)입니다. 단, 캠퍼스의 밖으로 이동할 수는 없습니다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해야합니다.

문제 풀이

간단한 bfs 문제입니다. 시험기간동안 제대로 문제를 풀지 못했는데 손풀기 문제로 적당했습니다.

1. 캠퍼스 크기와 도연이 친구 벽의 위치를 입력받습니다.

2. bfs 탐색을 하는데 가중치를 더해주는것이 아닌 친구를 만났을때만 cnt를 세어줍니다.

3. 탐색을 마치면 cnt가 0이하일경우 "TT"를 아닐 경우 만난 친구의 수를 출력합니다.

주의할 점

이 문제는 bfs로 풀어보았는데 dfs로도 풀 수 있을 것 같습니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

vector<vector<char>>v;
bool visit[601][601];
int n, m;
int a, b;
int cnt = 0;
string s;


void bfs(int y, int x)
{
	visit[y][x] = true;
	queue<pair<int, int>>q;
	q.push(make_pair(y, x));

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

		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny >= n || ny < 0 || nx >= m || nx < 0)
			{
				continue;
			}
			if (v[ny][nx] == 'X')
			{
				continue;
			}
			if (!visit[ny][nx])
			{
				if (v[ny][nx] == 'P')
				{
					cnt++;
				}
				visit[ny][nx] = true;
				q.push(make_pair(ny, nx));
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	v.resize(n, vector<char>(m));

	for (int i = 0; i < n; i++)
	{
		cin >> s;
		for (int j = 0; j < m; j++)
		{
			v[i][j] = s[j];
			if (v[i][j] == 'I')
			{
				a = i;
				b = j;
			}
		}
	}
	bfs(a, b);
	if (cnt <= 0)
	{
		cout << "TT";
	}
	else
	{
		cout << cnt;
	}
	return 0;
}

예제 1

3 5
OOOPO
OIOOX
OOOXP

결과 1

예제 2

3 3
IOX
OXP
XPP

결과 2