[알고리즘] 백준 1987번: 알파벳 (C++), 오류와 오류와 오류

이번 문제는 BFS로 풀려고 했다.

[당시 썼던 BFS 코드]

void bfs(int row, int col) {
	queue<pair<int, int>> q;
	q.push(make_pair(row, col));

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy >= 1 && dy <= n && dx >= 1 && dx <= m) {
				if (!visited[dy][dx] && alpha[map[dy][dx] - 64] == 0) {
					visited[dy][dx] = 1;
					alpha[map[dy][dx] - 64]++;
					mapPlus[dy][dx] = mapPlus[y][x] + 1;
					q.push(make_pair(dy, dx));
				}
			}
		}
	}
}

하지만 BFS의 특성으로 alpha 배열(visited의 역할)에서 이미 특정 알파벳이 나왔을 때 더 길을 나가지 못한다는 판단이 되어 DFS로 풀어야 하는 것을 알 수 있었다.

 

>> 앞 길에 'A'가 있는데 1, 1에서 출발한 길에선 아직 'A'가 나오지 않아서 가야 하지만 다른 길에서 이미 'A'가 나와서 가지 못하는 것으로 판단하는 것을 말한다.

 

---

[DFS를 사용한 이유]

BFS를 사용하면 여러 가지 길을 한 번에 검토하기 때문에 한 길에서 알파벳의 방문 여부를 확인 방법이 떠오르지 않았기 때문이다. 하지만 DFS도 다른 오류에서 똑같은 이유로 막혔었다.

 

당시의 코드를 보면 이렇다.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int n, m;
char map[21][21] = { 0, };
int mapPlus[21][21] = { 0, }; // 몇 번까지 가는지 cnt 전용 배열
bool alpha[27] = { 0, }; // alpha가 visited역할을 하기 때문에 visited는 필요없다

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // up down left right

void dfs(int row, int col) {
	for (int i = 0; i < 4; i++) {
		int dy = row + dir[i].y;
		int dx = col + dir[i].x;
		if (dy >= 1 && dy <= n && dx >= 1 && dx <= m) {
			int alphaIdx = map[dy][dx] - 64;
			if (alpha[alphaIdx] == 0) {
				//cout << "pass" << '\n';
				alpha[alphaIdx] = 1;
				mapPlus[dy][dx] = mapPlus[row][col] + 1;
				dfs(dy, dx);
				alpha[alphaIdx] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char idx;
			cin >> idx;
			map[i][j] = idx;
		}
	}
	
	alpha[map[1][1] - 64] = 1;
	mapPlus[1][1] = 1; // 말이 시작 위치 밟는 순간 1이기 때문이다.
	dfs(1, 1);

	int max = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mapPlus[i][j] > max) {
				max = mapPlus[i][j];
			}
		}
	}

	cout << max;
	return 0;
}

이 코드는 테스트 케이스를 통과하지만 결국에 정답이 될 수는 없다.

 

이유를 파악하기 위해 다음 코드를 작성하여 제일 긴 카운트가 어디서 발생하고 어떻게 긴 카운트로 도달하였는지 파악하려 했다.

for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << mapPlus[i][j] << ' ';
		}
		cout << '\n';
	}

 

다음 코드로 확인한 결과 이유를 파악할 수 있었다.

DFS를 다 끝낸 시점에서 최대 카운트는 다른 경로로 똑같은 자리에 최대 카운트를 덮어버릴 수 있다는 점이다.

 

>> 최댓값이 나올 때, DFS에서 최댓값을 담을 변수를 만들어주면 해결이 가능하다.

---

[정답 소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int n, m;
char map[21][21] = { 0, };
int mapPlus[21][21] = { 0, }; // 몇 번까지 가는지 cnt 전용 배열
bool alpha[27] = { 0, }; // alpha가 visited역할을 하기 때문에 visited는 필요없다

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // up down left right

/*
void bfs(int row, int col) {
	queue<pair<int, int>> q;
	q.push(make_pair(row, col));

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy >= 1 && dy <= n && dx >= 1 && dx <= m) {
				if (!visited[dy][dx] && alpha[map[dy][dx] - 64] == 0) {
					visited[dy][dx] = 1;
					alpha[map[dy][dx] - 64]++;
					mapPlus[dy][dx] = mapPlus[y][x] + 1;
					q.push(make_pair(dy, dx));
				}
			}
		}
	}
}
*/
int maxIdx = 1;
void dfs(int row, int col) {
	for (int i = 0; i < 4; i++) {
		int dy = row + dir[i].y;
		int dx = col + dir[i].x;
		if (dy >= 1 && dy <= n && dx >= 1 && dx <= m) {
			int alphaIdx = map[dy][dx] - 64;
			if (alpha[alphaIdx] == 0) {
				//cout << "pass" << '\n';
				alpha[alphaIdx] = 1;
				mapPlus[dy][dx] = mapPlus[row][col] + 1;
				if (mapPlus[dy][dx] > maxIdx) {
					maxIdx = mapPlus[dy][dx];
				}
				dfs(dy, dx);
				alpha[alphaIdx] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char idx;
			cin >> idx;
			map[i][j] = idx;
		}
	}

	alpha[map[1][1] - 64] = 1;
	mapPlus[1][1] = 1; // 말이 시작 위치 밟는 순간 1이기 때문이다.
	//bfs(1, 1);
	
	dfs(1, 1);

	cout << maxIdx;
	return 0;
}

---

[이번 문제에서 제일 중요했던 것]

이번 문제에서 제일 중요했던 건 'DFS까지 도달한 건 둘째이고, 최댓값을 어떻게 뽑아낼까'였다. 정말 간단하게 변수 선언해서 최댓값이면 넣어주는 문제이다.

 

>> 궁금한 것

최댓값 변수에 넣어주는 거 말고도 다른 방법도 있을까?

---

[변수가 모호하다.]

이번 문제에서 유독 계속 겪은 오류이다. 처음에 최댓값을 담는 변수 이름을 max라 짓고 넣으려 했지만 되지 않아서 maxArr(vector 배열)을 선언하고, 거기에 모든 값들을 담아 main에서 정렬하고 최댓값을 뽑아내려 했었다. 하지만, 이는 메모리 초과(쓸데없는 배열이라 그런 듯)를 일으킨다. 변수가 모호함은 main에서 알 수 있었다. 전역 변수로 선언하여 최댓값을 담으려 했던 변수 max와 지금은 main에 없지만 똑같은 이름의 로컬 변수 max(디버깅 출력용)이 있었다. 이를 파악하지 못하고, 시간을 허비했다.

 

>> 혹시나 하는 마음에 maxIdx로 변수를 바꿔주었다. (max라는 이름의 함수도 있어서)

 

---

[느낀 점]

너무 오랜만에 DFS or Backtracking을 사용해서 그런지 구현할 때 조금 거리낌이 있었다.

아직은 DFS와 BFS 중 어느 것을 사용해야 할지 핀트를 잘 잡아내지 못 하지만 이번 문제로 한 걸음 나아간다고 생각이 들었다.

 

궁금한 건 위에서 언급했듯 최댓값 변수 말고 다른 방법이 있을까?