문제 링크

👏 코드 설명

DFS를 이용하여 최대한 많이 갈수있는 경로를 찾는 문제다.
visit배열을 딕셔너리배열로 생각해서 대문자 각각을 index로 판단하여 지나왔던 알파벳은 1로 체크한다.

경로가 여러가지가 있을것이므로 지나왔던경로는 dfs 종료후 다시 visit배열을 0 으로 돌려보내줘야한다.

주의해야할점은 돌려보낼 때, cnt도 다시 돌아와야하므로 dfs(cnt+1) 형태로 써주어야한다.

😊 소스 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int r, c;
char map[21][21];
int visit[1000];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };

int answer;
void dfs(int y, int x,int cnt) {
	answer = max(answer, cnt);
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny >= r || ny < 0 || nx >= c || nx < 0) continue;
		if (visit[map[ny][nx]]==0) {
			visit[map[ny][nx]] = 1;
			
			dfs(ny, nx, cnt+1);
			visit[map[ny][nx]] = 0;
			
		}
	}
}
int main() {
	cin >> r >> c;
	for (int y = 0; y < r; y++) {
		for (int x = 0; x < c; x++) {
			cin >> map[y][x];
		}
	}
	
	visit[map[0][0]] = 1;
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
	using namespace std;
	int n, m, k;
	int map[101][101];
	bool visit[101][101];
	int dy[] = { -1,1,0,0 };
	int dx[] = { 0,0,1,-1 };
	vector<int> cost; //땅넓이
	int costt; //각각 땅 넓이
	void dfs(int y, int x) {

		costt++;
		visit[y][x] = true;
		for (int i = 0; i < 4; i++) {

			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || ny >= m || nx < 0 || nx >= n) continue;


			if (map[ny][nx] == 0 && !visit[ny][nx])
				dfs(ny, nx);

		}


	}

	int main() {
		int x1, x2, y1, y2;
		cin >> m >> n >> k;

		for (int i = 0; i < k; i++) {
			cin >> x1 >> y1 >> x2 >> y2;
			for (int y = m - y2; y < m - y1; y++) {
				for (int x = x1; x < x2; x++) {
					map[y][x] = 1;
				}
			}
		}
		int landcnt = 0;
		for (int y = 0; y < m; y++) {
			for (int x = 0; x < n; x++) {
				if (map[y][x] == 0 && !visit[y][x]) {
					landcnt++;
					costt = 0;
					dfs(y, x);
					cost.push_back(costt);
				}
			}
		}
		sort(cost.begin(), cost.end());

		cout << landcnt << endl;
		for (int i = 0; i < landcnt; i++) {
			cout << cost[i] << " ";
		}

		return 0;
	}
	dfs(0, 0,1);

	cout << answer;

	return 0;
}