(백준 1743번 음식물 피하기C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 3

이 기세를 몰아서 그대로~! 빡센 문제 하나 풀기 전에 몸풀기로 비슷한 문제를 하나 더 풀어보았다.

 

 

백준 1743번

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

1743번: 음식물 피하기

 

//1743번 음식물 피하기
#define  _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;


constexpr int MAX_N = 101;
class Graph {
public:
	int N, M;
	int arr[MAX_N][MAX_N] = { 0 };
	int dir_x[4] = { 0, 1, 0, -1 };
	int dir_y[4] = { 1, 0, -1, 0 };

	Graph() : N(0), M(0) {}
	Graph(int N, int M) : N(N), M(M) {}

	void addEdge(int x, int y) {
		arr[x][y] = 1;
	}
	bool isInside(int x, int y) {
		if (x <= 0 || y <= 0 || x > N || y > M) return false;
		return true;
	}
	int dfs_max(){
		int MAX = 1;
		// ★ 가로와 세로 ★
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (arr[i][j]) {
					MAX = max(dfs(i, j), MAX);
				}
			}
		}
		return MAX;
	}
private:
	int dfs(int x, int y) {
		int nodes = 1;
		arr[x][y] = 0;
		for (int i = 0; i < 4; i ++ ) {
			int x_next = x + dir_x[i];
			int y_next = y + dir_y[i];
			if (isInside(x_next, y_next) && arr[x_next][y_next]) {
				arr[x_next][y_next] = 0;
				nodes+= dfs(x_next, y_next);
			}
		}
		return nodes;
	}

};

int main() {
	int N, M, K;
	scanf("%d %d %d", &N, &M, &K);
	Graph g(N, M);
	for (int i = 0; i < K; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		g.addEdge(x, y);
	}
	printf("%d", g.dfs_max());
	return 0;

}

 

거의 80%쯤에서 오류가 생겨서 열심히 찾아보다가 아래 글을 보게 되었다.

 

https://www.acmicpc.net/board/view/70539

글 읽기 - 1743번 반례 좀 주세요

HOLYMOLY~~~~~

 

여기서의 교훈

가로와 세로, x오ㅏ y의 범위를 항상 조심하자