글 읽기 - [python] c++코드를 python으로 바꾸는 작업 중 시간초과가 뜹니다.

aaaa727 3년 전 0

안녕하세요.

c++로 제출한 코드 python으로 바꾸는 과정을 진행중입니다.

python을 잘 몰라서 어느부분에서 시간초과가 뜨는 지 잘 모르겠습니다.

pypy3은 속도가 빨라서 다행스럽게도 시간초과가 안뜨긴 하는데.. python의 함수들 시간복잡도좀 알려주시면 감사하겠습니다.

제 생각에는 2차원 list를 만들고 BFS에서 for문을 돌 때 의미없게 len(graph[n]) 만큼 돌아서 시간초과가 뜨는 것 같습니다.

고치고 있습니다.

import sys
#BFS
from collections import deque

def BFS(graph, root,visited):
    if(visited[root]==1):
        return 0
    queue = deque([root])
    visited[root]=1
    while queue:
        n = queue.popleft()
        for i in range (len(graph[n])):
            y  = graph[n][i]
            if(y != 0 and visited[y]==0): 
                queue.append(y)
                visited[y]=1
    return 1


n,m = map(int,input().split())
graph = [[0]* (n+1) for i in range(n+1)]
visited = [0] * (n+1) 
for i in range (0,m):
    first,second = map(int,input().split())
    graph[first][second] = second
    graph[second][first]= first

result = 0
for i in range (0,n+1):
    visited[i]=0
for i in range(1,n+1):
    if(visited[i]!=0):
        result= result + BFS(graph,i,visited)
print(result)



"""c++ 코드 로직입니다.
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
bool check[1001] = { false, };
vector<int>* vec;
int bfs(int start)
{
	if (check[start] == true)
		return 0;
	queue<int> q;
	q.push(start);
	check[start] = true;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < vec[x].size(); ++i)
		{
			int y = vec[x][i];
			if (!check[y])
			{
				q.push(y);
				check[y] = true;
			}
		}
	}
	return 1;
}

int main()
{
	int n, m;
	cin >> n>>m;

	vec = new vector<int>[n + 1];
	
	for (int i = 0; i < m; ++i)
	{
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int result = 0;
	for (int i = 1; i <= n; ++i)
	{
		result +=bfs(i);
 	}
	cout << result;
	delete[]vec;

}

"""

djm03178 3년 전 0

시간 복잡도가 적절하다고 해서 모든 언어로 반드시 통과된다는 보장은 없습니다.

Python 3가 그만큼 느리기 때문에 같은 시간 복잡도라고 해도 시간이 더 오래 걸리는 것뿐입니다.

물론 지금의 코드는 인접 행렬을 쓰고 있어 간선이 없는 부분까지 체크한다는 것이 경우에 따라서는 인접 리스트에 비해 비효율적일 수도 있으나, 어차피 이 문제는 최대 완전그래프가 될 수 있을 만큼 간선이 많을 수 있기 때문에 최악의 경우에는 결국 거의 동일한 수준으로 느려지게 될 것입니다.

djm03178 3년 전 1

대부분의 경우 PyPy3가 Python3보다 빠르므로 그냥 PyPy3만을 쓰시면 되고, Python3로 통과되지 않는다고 해서 틀린 코드라고 생각하실 필요는 없습니다. Python3의 태생적인 문제일 뿐입니다.

aaaa727 3년 전 0

말씀하신 부분을 알겠습니다. 최악의 경우가 있기에 어차피 코드를 고쳐도 달라질 것 같진 않다고 생각했습니다만, 위 코드는 정말 간단한 BFS 코드라서 일반적으로 python은 저런 간단한 코드도 시간초과가 뜨면 로직을 어떻게 구성해야할 지 답답한 마음이 있습니다.

c++로 BFS문제를 풀 때 거의 위와같은 로직을 사용했거든요.. 그래서 저 로직이 python으로 동작할 때 시간초과가 뜬다는 것은 제가 푼 거의 모든 문제가 python으로는 시간초과가 뜬다는 것이고요..

또한 1260 DFS와 BFS 문제 에서 c++에선 4ms 나던 코드가 python에서는 684ms 가 뜨는데 원래 이렇게 차이가 심한가요.?

그럼 보통 python 하시는 분들은 pypy3를 사용하시나요.? 그리고 코테에서 pypy3를 거의 지원하나요.?

답글 달아주셔서 감사합니다.

코테에서는 BOJ처럼 일괄적인 시간 보너스 공식을 만들어두지 않고 언어마다 여러 테스트를 통해 개별적으로 적절한 시간을 정하기 때문에 이런 문제를 겪을 일은 더 적을 거라고 봅니다. PyPy3를 보통 지원하는지는 잘 모르겠습니다. 그래도 이런 경우 조금 더 이득을 보시려면 파이썬에서 어떤 요소들이 특히 느린지 알아보고 최적화할 수 있는 여러 기법들을 알아보시는 것도 좋습니다.

파이썬은 대략 C++에 비해 약 30~100배 정도 느리다고 보니, 4ms가 684ms로 되는 건 놀라운 일은 아닙니다.

aaaa727 3년 전 0

친절한 설명 감사합니다. 저한테 뼈가되고 살이 되는 말들이었습니다.

좋은 하루되세요.

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

문제

문제

출처

ICPC

[python] c++코드를 python으로 바꾸는 작업 중 시간초과가 뜹니다.

aaaa727 3년 전 0

djm03178 3년 전 0

djm03178 3년 전 1

aaaa727 3년 전 0

djm03178 3년 전 2

aaaa727 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말