시작

이번 문제는 DFS를 이용해 푸는 문제다 그렇다면 한번 알아보자면, 이문제는 전에 풀었던 문제들처럼 연결된 컴포넌트를 찾는 문제가 아닌 계속 돌아다니다가 'P'를 찾으면 카운트하고 'X'를 찾으면 이동을 멈추는 문제다. 그렇다면 한번 간단하게 알고리즘을 작성을 해보자

알고리즘

1. 우선 문자 'I'를 찾는다.
2. 'I'를 기준으로 위아래왼쪽오른쪽을 탐색해나간다
3. 만약 탐색하는 곳에 방문을 했다면 continue
4. 만약 탐색하는 곳이 'X'라면 continue
5. 만약 탐색하는 'P'라면 카운트를 한다

이런식으로 알고맂므을 작성해보았는데. 한번 작성한 알고리즘으로 코드를 작성을 해보면..?

코드

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>

using namespace std;

int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
// Y, X
int N, M, result = 0;
vector<string> _map;
vector<vector<int>> visited;

void DFS(int x, int y) {
	// 만약 조건에 안맞으면 넘기기
	if (visited[y][x] == 1 || _map	[y][x] == 'X') return;
	visited[y][x] = 1;
	// 만약 사람과 만났다면 카운트
	if (_map[y][x] == 'P') result++;

	// 탐색하기
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		// 범위를 벗어난다면 continue;
		if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
		DFS(nx, ny);
	}
} 


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;
	_map.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++)
		visited[i].resize(M);

	for (int i = 0; i < N; i++) {
		cin >> _map[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			// 'I'를 찾는다.
			if (_map[i][j] == 'I') {
				DFS(j, i);
				break;
			}
		}
	}

	// 만약 1이상이라면 result출력 만약 0이면 TT출력
	if (result)cout << result;
	else cout << "TT";
}

cpp치곤 메모리와 시간을 많이 먹었지만 최적화를 실행하면 더욱 빠르고 적은 메모리를 쓰는 코드가 완성이 될 것.