[Algorithm]Baekjoon 1987번 : 알파벳

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

1987번: 알파벳

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
 
using namespace std;
 
int maxRow;
int maxColumn;
char board[20][20] = { 0 };
int answer = 0;
int totalSize = 0;
map<char, bool> check;
 
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; // 상하좌우
 
void solution(int row, int column, int count)
{
    if (answer == totalSize) return;
    check[board[row][column]] = true;
    count += 1;
    if (count >= answer) answer = count;
 
    for (int i = 0; i < 4; i++)
    {
        int nextRow = row + dir[i][0];
        int nextCol = column + dir[i][1];
 
        if (nextRow < 0 || nextRow >= maxRow) continue;
        if (nextCol < 0 || nextCol >= maxColumn) continue;
        if (check[board[nextRow][nextCol]]) continue;
 
        solution(nextRow, nextCol, count);
        check[board[nextRow][nextCol]] = false;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int row = 0;
    int column = 0;
    char input = 0;
 
    cin >> row >> column;
 
    maxRow = row;
    maxColumn = column;
 
    map<char, bool> tempCheck;
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < column; j++)
        {
            cin >> board[i][j];
            if (!tempCheck[board[i][j]])
            {
                totalSize++;
                tempCheck[board[i][j]] = true;
            }
        }
    }
 
    solution(0, 0, 0);
 
    cout << answer;
}
 

이 문제도 어렵진 않은 문젠데, 처음에 제출을 했을 때 시간초과에 걸렸었다.

check변수를 전역적으로 안쓰고 매개변수로 각 함수호출마다 복사해서 쓰는 방식으로 체크했더니 시간초과에 걸렸었다.

 

함수호출할 조건을 체크하는 부분도 (행,열크기,방문검사) 저렇게 안하고 호출함수 첫부분에 했었는데, 생각해보니 그렇게 하면 함수에 들어가자마자 거의 바로 리턴되긴하더라도, 어쨌든 함수호출 자체는 모든경우에 다 해버리기 때문에 매개변수의 check변수를 모든 경우에 다 복사해버린다. 함수호출자체도 결국 코스트가 있는 행위이기 때문에, 앞으로 문제 풀 때는 하면 안될 것 같다.

 

if(answer == totalSize) return; 

-> 이부분은 결국 answer이 보드의 최대 중복되지 않는 알파벳개수가 된다면, 더이상 늘어날 일이 없기 때문에 작성한건데

딱히 시간이 더 줄거나 하진 않았다. 조금이라도 줄면 그러려니 하는데, 오히려 늘어났다;;