BOJ 21736 - 헌내기는 친구가 필요해

문제

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

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

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

#include <iostream>
using namespace std;
 
const int MAXN = 601;
char campus[MAXN][MAXN];
bool visit[MAXN][MAXN];
 
int n, m, x, y, cnt;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
 
void dfs(int x, int y) {
	visit[x][y] = true;
		
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
			
		if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
			if (campus[nx][ny] != 'X' && !visit[nx][ny]) {
				
				if (campus[nx][ny] == 'P')
					cnt++;
 
				dfs(nx, ny);
			}
		}			
	}
 
	return;
}
 
void solve() {
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> campus[i][j];
 
			if (campus[i][j] == 'I') {
				x = i;
				y = j;
			}
		}
	}
 
	dfs(x, y);
	
	if (cnt == 0)
		cout << "TT" << '\n';
	else
		cout << cnt << '\n';
}
 
int main() {
    
    ios_base::sync_with_stdio(false);	
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도

시간 복잡도: 캠퍼스의 모든 칸을 DFS로 한 번씩 확인하므로 $O(NM)$ 이다.
공간 복잡도: 방문 배열과 재귀 호출 스택을 사용하므로 $O(NM)$ 이다.

마무리

출발점에서 닿을 수 있는 영역만 보면 되므로 탐색 시작점은 하나다. 벽을 제외한 칸을 DFS로 퍼져 나가며 만나는 사람 수만 세면 된다.

BOJ 21736 - 헌내기는 친구가 필요해

문제

입력

출력

풀이

코드

복잡도

마무리

문제#

입력#

출력#

풀이#

코드#

복잡도#

마무리#

문제

입력

출력

풀이

코드

복잡도

마무리