[BOJ] 백준 #1743. 음식물 피하기 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/1743

• 알고리즘 분류: 깊이 우선 탐색 (DFS)
• 난이도: Silver Ⅰ

💬 풀이

1. 음식물이 떨어진 좌표를 이차원 배열에 저장
2. 저장된 좌표들을 대상으로 DFS를 이용해 맞닿아있는 음식물 수를 카운트
3. 걔네 중 가장 큰 값 출력

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX 101
using namespace std;

int N, M, K;
bool map[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int cnt = 0;

void DFS(int y, int x) {
	visited[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 1 || nx < 1 || ny > N || nx > M) { continue; }
		if (map[ny][nx] && !visited[ny][nx]) {
			cnt++;
			DFS(ny, nx);
		}
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	cin >> N >> M >> K;
	int r, c;
	while (K--) {
		cin >> r >> c;
		map[r][c] = true;
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (map[i][j] && !visited[i][j]) {
				cnt = 1;
				DFS(i, j);
				ans = max(ans, cnt);
			}
		}
	}
	cout << ans;

	return 0;
}