[ 백준 BOJ / c++ ] 21736번 헌내기는 친구가 필요해

 

🤔 문제

 

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

 

---

👀 접근 방식

처음에는 모든 배열에 대해 이중 for문으로 검사해 구하려 하였으나, 벽이 크게 쳐져 있는 경우에 대해서 예외처리하기 어렵다 생각을 해, DFS 방식으로 푸는 것으로 방향을 잡았다

1. 캠퍼스 정보를 입력받고, "I" 가 입력 되었을때 도연이의 위치를 저장한다.
2. 도연이 현재 위치부터 상하좌우를 움직여 모든 위치로 움직인다.
3. X( 벽 ) 이거나 이미 방문한 위치일 시 움직이지 않는다.
4. P( 사람 ) 일 경우 answer( 만난 사람 수 )를 1 증가한다

---

💻 코드

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

using namespace std;

int answer = 0;
int n, m;

bool visit[601][601];
char maps[601][601];

void process(int y, int x)
{
	// 현재위치가 방문 되었으면 종료
	if (visit[y][x])
	{
		return;
	}
	else {
		// 현재위치가 미방문 상태이면 방문으로 바꿈
		visit[y][x] = 1;

		// P, 즉 사람일 시 만났으므로 answer 1 증가
		if (maps[y][x] == 'P')
			answer++;

		// X는 장애물이므로 X가 아닐시에만 재귀함수 실행
		if (maps[y][x] != 'X')
		{
			// 왼쪽 이동 ( if문은 배열 범위 초과 방지 )
			if (x - 1 >= 0)
				process(y, x - 1);

			// 오른쪽 이동 ( if문은 배열 범위 초과 방지 )
			if (x + 1 < m)
				process(y, x + 1);

			// 위쪽 이동 ( if문은 배열 범위 초과 방지 )
			if (y - 1 >= 0)
				process(y-1, x);

			// 아래쪽 이동 ( if문은 배열 범위 초과 방지 )
			if (y + 1 < n)
				process(y + 1, x);

		}
	}

}

int main()
{ 
	// 캠퍼스 크기 입력 받기
	cin >> n >> m;

	// 주인공 위치를 담을 변수 선언
	int x = 0, y = 0;

	// 캠퍼스 정보 입력받기
	for (int i = 0; i < n; ++i)
	{
		// 문자열로 입력받아 문자로 쪼개기
		string input;
		cin >> input;

		for (int j = 0; j < input.length(); ++j)
		{
			maps[i][j] = input[j];
			// I는 주인공이므로 위치 저장
			if (input[j] == 'I')
			{
				x = j;
				y = i;
			}
		}
	}

	// 현재 주인공 위치에서 이동 시작
	process(y, x);

	// 출력
	if(answer)
		cout << answer;
	else 
		cout << "TT";

	return 0;
}