C++ / 백준 / 1987 / 알파벳

문제

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

1987번: 알파벳

문제풀이

BFS로 풀었다가 메모리 초과가 났고, DFS로 풀었다가 시간 초과가 났다.

질문글을 보니 DFS에 벡터를 넣어 벡터를 복사하게 되면 시간이 더 걸리므로 전역으로 선언하는 것이 좋다고 했다.

그 부분을 수정했더니 통과가 됐다.

크게 어려운 부분은 없다.

0, 0부터 시작하여 DFS로 모든 경우를 탐방하는데 이미 지나갔던 알파벳이 있는 곳은 가지 못하도록 조건만 걸면 된다.

visti벡터를 bool형으로 alp로 선언했다.

board는 char형으로 받았기 때문에 alp를 확인할 때는 65를 빼어 A=0 ~ Z=25로 바꿔 판별하였다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>>loc = { {-1,0},{1,0},{0,-1},{0,1} };
vector<vector<char>>board;
vector<bool>alp(26, false);
int R, C;
int answer;

void DFS(int y,int x,int cnt) {
	answer = max(answer, cnt);
	int idx(0);
	for (idx = 0; idx < 4; ++idx) {
		int n_y(y + loc[idx][0]);
		int n_x(x + loc[idx][1]);
		if (n_y >= 0 && n_y < R && n_x >= 0 && n_x < C) {
			if (!alp[board[n_y][n_x] - 65]) {
				alp[board[n_y][n_x] - 65] = true;
				DFS(n_y, n_x, cnt + 1);
				alp[board[n_y][n_x] - 65] = false;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> R >> C;
	board = vector<vector<char>>(R, vector<char>(C, ' '));
	int y(0), x(0);
	for (y = 0; y < R; ++y)
		for (x = 0; x < C; ++x)
			cin >> board[y][x];
	
	alp[board[0][0]-65] = true;
	DFS(0,0,1);
	cout << answer;
}