헌내기는 친구가 필요해

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (하단 참고)	1024 MB	3403	1990	1668	60.943%

문제

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다.

드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 

도연이가 다니는 대학의 캠퍼스는 N x M 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다.

예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1, y), (x, y+1), (x-1, y), (x, y-1)이다.

단, 캠퍼스의 밖으로 이동할 수는 없다.

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

입력

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N (1 ≤ N ≤ 600), M (1 ≤ M ≤ 600)이 주어진다.

둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. 

O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. 

I가 한 번만 주어짐이 보장된다.

출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다.

단, 아무도 만나지 못한 경우 TT를 출력한다.

예제 입력 1

3 5
OOOPO
OIOOX
OOOXP

예제 출력 1

1

예제 입력 2

3 3
IOX
OXP
XPP

예제 출력 2

TT

출처

University > 숙명여자대학교 > 제1회 숙명여자대학교 교내 알고리즘 경진대회 (SMUPC) C번

• 문제를 검수한 사람: cs71107, lky7674, plast, sait2000, songfox00, wbcho0504, whaeun25
• 문제를 만든 사람: swoon

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

통과된 코드

DFS 탐색을 재귀로 구현하여 문제를 해결

#include <iostream>
using namespace std;
int _Res = 0, _N, _M;
int _DxDy[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
char _Map[600][600];
string _Str;
char _Temp;
pair<int, int> StartPos;

// 재귀를 이용한 DFS (Depth-First Search) 탐색 
void DFSSearch(int _CntX, int _CntY)
{
	for (int j = 0; j < 4; j++) {
		int _dx = _CntX + _DxDy[j][0];
		int _dy = _CntY + _DxDy[j][1];
		if (_dx >= _N || _dy >= _M || _dx < 0 || _dy < 0)
			continue;
		if (_Map[_dx][_dy] == 'X')
			continue;
		if (_Map[_dx][_dy] == 'P')
			_Res++;
		// 방문처리 대신에 X(벽)으로 마킹
		_Map[_dx][_dy] = 'X';
		DFSSearch(_dx, _dy);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N >> _M;
	for (int i = 0; i < _N; i++) {
		cin >> _Str;
		for (int j = 0; j < _M; j++) {
			_Map[i][j] = _Str[j];
			if (_Str[j] == 'I') {
				StartPos = make_pair(i, j);
				_Map[i][j] = 'X';
			}
		}
	}
	
	DFSSearch(StartPos.first, StartPos.second);

	if (_Res == 0) cout << "TT"; 
	else  cout << _Res;

	return 0;
}