글 읽기 - 파이썬 질문 있습니다.

hello70825 5년 전 0

제가 맞은 코드로는 python으로 제출하면 시간 초과로 통과를 못합니다.

그래서 @jh05013 님의 코드를 보니 for문을 이용해 통과를 하셨던데요.

제 생각엔 while, for 차이 밖에 없는 것 같은데 어디에서 약 두 배의 시간 차이가 나는 것인지 잘 모르겠습니다.

for문으로 푸신 조건을 while문으로 옮겨 적어도 시간 초과가 나오네요..

그리고 문제와는 상관 없지만 저는 bfs를 풀 때 continue, break를 여러 번 쓰기보다는 조건을 한 줄에 다 쓰고(너무 길면 두 줄에 걸쳐서)

이 조건을 만족하면 큐에 추가하는 방식을 사용하고 있는데 이게 continue, break를 사용하는 것보다 비효율적인 코드인가요?

#for문
from collections import deque
MIS = lambda: map(int,input().split())
di = (-1,1,0,0)
dj = (0,0,-1,1)

n, m, limit = MIS()
grid = [input() for i in range(n)]
i1, j1, i2, j2 = MIS()
vis = [[-1]*m for i in range(n)]; vis[i1-1][j1-1] = 0
Q = deque([(i1-1, j1-1)])
while Q:
    i, j = Q.popleft()
    for d in range(4):
        for k in range(1, limit+1):
            ni, nj = i+k*di[d], j+k*dj[d]
            if not (0<=ni<n and 0<=nj<m) or grid[ni][nj] == '#': break
            if -1 != vis[ni][nj] <= vis[i][j]: break
            if -1 != vis[ni][nj]: continue
            vis[ni][nj] = vis[i][j]+1; Q.append((ni,nj))
print(vis[i2-1][j2-1])


#while 문
from collections import deque
input=__import__('sys').stdin.readline
dx, dy=[0,0,1,-1], [1,-1,0,0]
n, m, k=map(int,input().split())
D=[input().strip() for _ in range(n)]
sx, sy, ex, ey=map(int,input().split())
sx-=1; sy-=1; ex-=1; ey-=1
S=[[-1]*m for _ in range(n)]
q=deque([(sx, sy)])
S[sx][sy]=0
while q:
    x, y=q.popleft()
    for i in range(4):
        nx, ny=x+dx[i], y+dy[i]
        nk=1
        while nk<=k and 0<=nx<n and 0<=ny<m and D[nx][ny]!='#':
            if S[nx][ny]==-1:
                q.append((nx, ny))
                S[nx][ny]=S[x][y]+1
            nx+=dx[i]; ny+=dy[i]; nk+=1
print(S[ex][ey])

#for문으로 통과한 코드 일부를 while문으로 바꿔적으면 시간 초과가 나는 코드
from collections import deque
input=__import__('sys').stdin.readline
n,m,k=map(int,input().split())
D=[input().strip() for _ in range(n)]
sx,sy,ex,ey=map(int,input().split())
sx-=1;sy-=1;ex-=1;ey-=1
S=[[-1]*m for _ in range(n)]
q=deque([(sx,sy)])
S[sx][sy]=0
dx,dy=[0,0,1,-1],[1,-1,0,0]
while q:
    x,y=q.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i];nk=1
        while 1:
            if nk>k or nx>=n or nx<0 or ny<0 or ny>=m:break
            if D[nx][ny]=='#':break
            if -1 != S[nx][ny] <=S[x][y]:break
            if -1 != S[nx][ny]:continue
            q.append((nx,ny))
            S[nx][ny]=S[x][y]+1
            nx+=dx[i]; ny+=dy[i]; nk+=1
print(S[ex][ey])

두 번째 코드는 O(NMK)의 시간복잡도를 가져서 시간 초과가 나는데, 놀랍게도 첫 번째 코드의 "if -1 != vis[ni][nj] <= vis[i][j]: break"를 넣으면 O(NM)으로 줄어듭니다. 왜 이걸 넣어도 올바른지와 왜 O(NM)이 되는지 생각해 보는 것도 재미있는 문제인 것 같습니다. 세 번째 코드가 시간 초과인 이유는 눈으로만 봐선 모르겠네요.

continue와 break의 사용은 효율 문제보다는 취향 차이인 것 같습니다. 저는 들여쓰기가 많지 않은 것을 선호하기 때문에 이 둘을 자주 씁니다. 짧은 줄들을 세미콜론으로 이어붙이는 것도 제 취향에 따른 거지만 사실 바람직한 코딩 스타일은 아닙니다.

hello70825 5년 전 0

정말 감사합니다. 항상 배우고 갑니다.

고민을 하다가 생각난건데 https://www.acmicpc.net/proble... 이 문제와 푸는 방법이 똑같군요

날 잡고 전체적으로 문제를 다시 풀어봐야 할 필요성을 느끼네요. 다시 한 번 감사드립니다.

jh05013 5년 전 2

@nova9128 코드를 베껴서 맞지 말아 주세요. 심할 경우 아이디 삭제까지 갈 수 있는 행위입니다.

nova9128 5년 전 0

@jh05013

아네 주의하도록 할께요.

파이썬이 느린걸알아서 시간이야기 나오면 궁금해서 이렇게 저렇게 조금이라도 빠를까 실험중이라서요.

hello70825 5년 전 1

while문을 이용해 python도 통과시켰습니다 ㅎㅎ

숏코딩을 python으로 해두고 싶은데 탭 대신 스페이스 한 칸으로 하지 않는 이상 python으로 못 해둘 것 같네요 :(

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

문제

문제

출처

ICPC

파이썬 질문 있습니다.

hello70825 5년 전 0

jh05013 5년 전 4

hello70825 5년 전 0

jh05013 5년 전 2

nova9128 5년 전 0

hello70825 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말