글 읽기 - 어떤부분이 차이가 나는지 알 수 있을까요?

jh0956 4년 전 0

약 10번? 의 시도끝에 문제를 해결했습니다.

그런데 채점현황을 보니

제 코드가 다른 분들 코드에 비해 5~10배가량 늦더라구요

풀었다는거에 안주하지않고 왜 느린건지 짚은 후에 넘어가고 싶어서 검색을 해보았습니다.

하지만 코드의 흐름이 거의 비슷한거같아서.. 도저히 어떤 부분에서 시간이 느린건지

다음에 이런 탐색문제를 풀때도 참고할 수 있을 것 같아 질문드립니다.

윗 부분이 제 코드, 아랫 부분이 검색해서 긁어온 코드입니다.

짚어주시면 감사하겠습니다.

// 구현한 소스

// bfs 로는 시간초과를 어떻게 해결해야할지 모르겠다
// dfs 로 탐색해가면서 인덱스 별로 값을 매기는 dp식으로 구현하면 해결될까?
#include <iostream>
#include <string>
using namespace std;

// 최대길이가 80이니 100 100 80으로 잡음
int dp[100][100][80];
char arr[100][100];
int mx[4] = { -1,1,0,0 };
int my[4] = { 0,0,1,-1 };
int N, M, K;
string ans;

int solve(string str, int y, int x, int idx) {

	if (dp[y][x][idx] != -1) return dp[y][x][idx];

	if (str.size() >= ans.size()) return 1;
	dp[y][x][idx] = 0;
	for (int i = 0; i < 4; i++) {
		int yy = y, xx = x;
		for (int j = 1; j <= K; j++) {
			yy += my[i];
			xx += mx[i];
			if (yy >= 0 && xx >= 0 && yy < N && xx < M && arr[yy][xx] == ans[idx+1]) {
				dp[y][x][idx] += solve(str + ans[idx+1], yy, xx, idx + 1);
			}
		}
	}

	return dp[y][x][idx];
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> arr[i][j];

	cin >> ans;

	int total = 0;
	string f;
	f.push_back(ans[0]);

	for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) for (int k = 0; k < 80; k++) dp[i][j][k] = -1;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] == ans[0]) {
				total += solve(f, i, j, 0);
			}
		}
	}

	cout << total;
	return 0;
}
///////////////////////////

// 검색해본 소스 ////
#include<iostream>
#include<cstring>
#include<string>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, M, K, Answer;
char MAP[MAX][MAX];
int DP[MAX][MAX][80];
 
string Dest;
int Dest_Len;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
    cin >> Dest;
    Dest_Len = Dest.length();
    memset(DP, -1, sizeof(DP));
}
 
int DFS(int x, int y, int Idx)
{
    if (DP[x][y][Idx] != -1) return DP[x][y][Idx];
    if (Idx >= Dest_Len) return 1;
 
    DP[x][y][Idx] = 0;
    for (int i = 0; i < 4; i++)
    {
        for (int k = 1; k <= K; k++)
        {
            int nx = x + dx[i] * k;
            int ny = y + dy[i] * k;
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (MAP[nx][ny] != Dest[Idx]) continue;
 
            DP[x][y][Idx] = DP[x][y][Idx] + DFS(nx, ny, Idx + 1);
        }
    }
    return DP[x][y][Idx];
}
 
void Solution()
{
    char Temp = Dest[0];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == Temp)
            {
                Answer = Answer + DFS(i, j, 1);
            }
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

rlarlghks970113 4년 전 0

제 부족한 지식으로 답변드리자면

질문의 위 아래 코드 둘 다 dfs를 이용해서 푸셔서 결과적으로 똑같은 코드입니다.

dfs와 bfs의 시간초과 차이가 나는 이유는 메모이제이션을 이용하고 말고의 차이 아닐까요?

메모이제이션 기법을 이용하면 중첩되는 계산을 단 한 번만 계산하게되는 최적화가 일어나서 시간초과가 안납니다.

시간복잡도로 계산하면 O(정답 문자열의 길이 * 정답의 갯수)정도로 계산하면 되겠네요.

저도 bfs에 메모이제이션을 적용하는 법을 고민했는데 생각이 안나더라고요.

푸는 법을 곰곰히 고민하다가 깃허브와 구글에 검색해봐도 bfs로 푸신 분이 없는 걸로 보아 bfs로는 풀기 어려운 걸로 보입니다.

아마 문제분류의 bfs를 보고 고민하신거 같은데 그냥 dfs, dp문제로 이해하시고 넘어가면 될 거 같습니다.

제가 답변한 것에 틀린게 있다면 댓글 달아주세요 :)

jh0956 4년 전 0

답변 감사드립니다!

bfs 로는 안될거같아서 dfs로 풀다가 시간오버가 뜨길래

메모이제이션을 적용했더니 깔끔하게 통과하더라구요. 말씀해주신대로 dfs,dp문제로 이해하고 넘어가려구요 ㅎㅎㅎ

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

문제

문제

출처

ICPC

어떤부분이 차이가 나는지 알 수 있을까요?

jh0956 4년 전 0

rlarlghks970113 4년 전 0

jh0956 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말