[C++] 1987: 알파벳

골드 Ⅳ

 

#include <iostream>
#include <queue>
using namespace std;
int R, C;

char map[20][20];
char str[21];
bool visit[26];
priority_queue<int> max_heap;

void backtrack(int i, int j, int c) {
	printf("--> %c (%d, %d) 옴\n -- depth : %d\n", map[i][j], i, j, c);
	//벗어난 경우
	if (i < 0 || i >= R || j < 0 || j >= C) {
		int t = max_heap.top();
		printf("top : %d\n", t);
		printf("cnt : %d\n", c);
		if (c > t) {
			max_heap.push(c);
			printf("%d 넣음\n", c);
		}
		return;
	}
	//지나왔던 알파벳일 경우
	if (visit[map[i][j] - 'A']) {
		int t = max_heap.top();
		printf("top : %d\n", t);
		printf("cnt : %d\n", c);
		if (c > t) {
			max_heap.push(c);
			printf("%d 넣음\n", c);
		}
		return;
	}

	//밟고 지나가기
	visit[map[i][j] - 'A'] = true;
	int cnt = ++c;

	backtrack(i - 1, j, cnt);//상
	backtrack(i + 1, j, cnt);//하
	backtrack(i, j - 1, cnt);//좌
	backtrack(i, j + 1, cnt);//우

	visit[map[i][j] - 'A'] = false;
}


int main() {
	scanf("%d%d", &R, &C);

	max_heap.push(-1);
	for (int i = 0; i < R; i++) {
		scanf("%s", str);
		for (int j = 0; j < C; j++) {
			map[i][j] = str[j];
		}
	}

	backtrack(0, 0, 0);
	int ans = max_heap.top();
	printf("%d\n", ans);
}

 

백트래킹 문제

 

스택을 줄이려면 재귀 자체를 줄여야 하니까

backtrack으로 무조건 상하좌우 들어가기 전에 if문으로 확인하는 식으로 하면

(위의 코드는 일단 상하좌우 들어가고 빠져나갔는지 or 왔던데인지 확인)

좋을 것 같기두 하구

 

-> 해서 가져옴

#include <iostream>
#include <queue>
using namespace std;
int R, C;

char map[20][20];
char str[21];
bool visit[26];
int ans = -1;

int delta[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };

void backtrack(int i, int j, int c) {

	//일단 밟기
	visit[map[i][j] - 'A'] = true;
	int cnt = c + 1;

	//상하좌우 보기
	for (int k = 0; k < 4; k++) {
		int ni = i + delta[k][0];
		int nj = j + delta[k][1];

		//갔던 데 이거나 넘어간다면
		if (visit[map[ni][nj] - 'A'] || ni < 0 || ni >= R || nj < 0 || nj >= C) {
			if (cnt > ans) ans = cnt;
		}
		else backtrack(ni, nj, cnt);
	}
	visit[map[i][j] - 'A'] = false;
}


int main() {
	scanf("%d%d", &R, &C);

	for (int i = 0; i < R; i++) {
		scanf("%s", str);
		for (int j = 0; j < C; j++) {
			map[i][j] = str[j];
		}
	}

	backtrack(0, 0, 0);
	printf("%d", ans);
}

cnt 세주는 방식 바뀐거 말고 특이점 없음

 

dfs 상하좌우 해주고

visit[map[i][j] - 'A'] = false; 하는게 제일 포인트임!!