백준 1987번 알파벳 C++

리뷰

시간 진짜 간당간당했다.. 방문 처리 배열 크기를 대충 100으로 잡았다가 시간초과가 떠서 범위에 딱 맞게 사용하니 통과되었다.

 

문제 풀이

1. n * m 크기의 필드를 받아준다. 필드는 문자열 이므로 n크기의 1차원 배열로 초기화 해주면 된다.
2. 좌상단을 방문처리 해주고 dfs를 실행한다, 이때 필드는 주소 참조를, 방문처리는 새로운 리스트를 계속 만들어줬다.
3. 이후 4방향을 돌며 다음 좌표가 방문처리가 되지 않았다면 방문 처리 후 dfs 실행, 이후 방문처리를 다시 지워준다.
4. 더 이상 진행할 방향이 없어 for루프가 종료되면 현재 누적된 cnt를 ans와 비교하여 값을 갱신해 준다.
5. dfs가 완전 종료된 이후 ans에 저장된 모든 cnt의 max값을 출력해 주면 된다.

 

참고 사항

방문 배열의 인덱스를 넉넉하게 주지 말고 타이트하게 초기화 해주자 나는 이 차이로 시간초과 여부가 갈렸다.

 

 

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, ans = 0;
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

void dfs(vector<string>& lst, vector<int> v, int x, int y, int cnt) {
	cnt++;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[lst[nx][ny] - 65]) {
			v[lst[nx][ny] - 65] = 1;
			dfs(lst, v, nx, ny, cnt);
			v[lst[nx][ny] - 65] = 0;
		}
	}
	ans = max(ans, cnt);
}

int main() {
	cin >> n >> m;
	vector<string> lst(n);
	vector<int> v(26, 0);
	for (int i = 0; i < n; i++) {
		cin >> lst[i];
	}
	v[lst[0][0] - 65] = 1;
	dfs(lst, v, 0, 0, 0);
	cout << ans;
}