글 읽기 - c++ 고수님들 도와주세요..(시간초과)

sls666 3년 전 0

8%때에서 시간초과가 발생합니다. 다른 정답코드들도 비슷한 로직을 사용하여 구현을 했는데, 왜 이 코드는 시간초과가 발생할까요????

정답코드는 map대신 벡터로 중복 체크를 한것 말고는 비슷하다고 생각합니다!!

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#define endl '\n';

using namespace std;

int R, C, answer;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
vector<string> map;
unordered_map<char, int> m;

void input() {
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		string tmp;
		cin >> tmp;
		map.push_back(tmp);
	}
}

void firstSetting() {
	m[map[0][0]] = 1;
}

void solve(unordered_map<char, int>& m, int curX, int curY, int cnt) {
	if (answer < cnt) {
		answer = cnt;
	}

	for (int i = 0; i < 4; i++) {
		int nx = curX + dx[i];
		int ny = curY + dy[i];

		if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
		if (m.count(map[nx][ny]) == 0) {
			m[map[nx][ny]] = 1;
			solve(m, nx, ny, cnt + 1);
			m.erase(map[nx][ny]);
		}
	}

}

int main() {
	input();
	firstSetting();

	solve(m, 0, 0, 1);
	cout << answer << endl;

	return 0;
}

/* 참조한 정답코드
 *
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n, m;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int go(vector<string> &board, vector<bool> &check, int x, int y) {
    int ans = 0;
    for (int k=0; k<4; k++) {
        int nx = x+dx[k];
        int ny = y+dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
            if (check[board[nx][ny]-'A'] == false) {
                check[board[nx][ny]-'A'] = true;
                int next = go(board, check, nx, ny);
                if (ans < next) {
                    ans = next;
                }
                check[board[nx][ny]-'A'] = false;
            }
        }
    }
    return ans + 1;
}
int main() {
    cin >> n >> m;
    vector<string> board(n);
    for (int i=0; i<n; i++) {
        cin >> board[i];
    }
    vector<bool> check(26);
    check[board[0][0]-'A'] = true;
    cout << go(board, check, 0, 0) << '\n';
    return 0;
}

*/

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 고수님들 도와주세요..(시간초과)

sls666 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말