글 읽기 - 여러번 수정해봤지만 계속 시간초과가 나옵니다 ㅠ 문제가 뭘까요...

hyong11 1년 전 0

일단 문제에서 주어진 테스트 케이스는 전부 맞습니다.

input()도 readline으로 바꿔보았고 처음에 miro 리스트 받을 때 int로 일일이 수정했던 코드도 그냥 str로 받아 바로 적용도 해봤는데 여전히 시간초과가 납니다..

pypy3로도 해봤지만 이경우는 메모리 초과가 나오더라구요 ㅠ

몇시간동안 계속 붙잡고있으니 정신 나갈 거 같습니다,,

도와주시면 감사하겠습니다!

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())

dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)

miro = [input() for _ in range(n)]

#미로의 요소가 격자 범위를 넘어서지 않고, 1인 경우에만 이동 가능하도록
def is_valid_coord(y, x):
    return 0 <= y < n and 0 <= x < m and miro[y][x] == '1'

#이미 지나간 길인지 체크하기 위한 리스트
chk = [[False] * m for _ in range(n)]


def bfs(start_y, start_x):
    q = deque()
    cnt = 1
    q.append((start_y, start_x, cnt))
    #초기 위치는 이미 지나간 길로 간주
    chk[0][0]=True
    while q:
        y, x, cnt = q.popleft()
        if y == n - 1 and x == m - 1:
            return cnt
        for k in range(4):
            next_y = y + dy[k]
            next_x = x + dx[k]
            if is_valid_coord(next_y, next_x) and not chk[next_y][next_x]:
                #조건에 부합하면 해당 요소로 이동함
                chk[y][x] = True
                q.append((next_y, next_x, cnt+1))

print(bfs(0,0))

eatingnut 1년 전 1

35번 줄에 오류가 있네요. 저 부분만 어떻게 고쳐 보세요!

hyong11 1년 전 0

@eatingnut 답변 감사합니다!

해당 부분 chk[y][x] = True => chk[next_y][next_x]로 바꾸니 맞췄습니다.
답변 덕분에 왜 시간 초과가 나게 되었는지 이유를 알 수 있었습니다.

그리고 추가로 궁금한 점이 생겼는데요

제가 질문글에 코드를 여러번 수정했다고 말씀드렸습니다만 체크리스트를 True로 바꾸는 코드 즉, chk[y][k] = True를 30번 줄에 쓰느냐, chk[next_y][next_x] = True를35 번에 쓰느냐에 따라 전자는 시간초과, 후자는 정답처리가 되었습니다.

제가 생각하기엔 두가지 경우 모두 다 논리적으로는 문제가 없을 뿐더러 실행시간도 왜 차이가 나는지 모르겠습니다.

두 경우의 차이점이라면 조건에 부합하는 좌표를 deque에 append시킨 후 그 좌표를 지나온 좌표로 간주하거나, append하기 전에 지나온 좌표로 간주한다는 것인데

단순히 코드 순서차이만으로 성능이 왜 차이가 나는 걸까요??

혹시 몰라 정답코드와 오답코드 게시하겠습니다.

답변부탁드립니다 ㅠㅠ

#########정답 코드#########
import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())

dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)

miro = [input() for _ in range(n)]
    
def is_valid_coord(y, x):
    return 0 <= y < n and 0 <= x < m and miro[y][x] == '1'

chk = [[False] * m for _ in range(n)]


def bfs(start_y, start_x):
    q = deque()
    cnt = 1
    q.append((start_y, start_x, cnt))
    chk[0][0]=True
    while q:
        y, x, cnt = q.popleft()
        if y == n - 1 and x == m - 1:
            return cnt
        for k in range(4):
            next_y = y + dy[k]
            next_x = x + dx[k]
            if is_valid_coord(next_y, next_x) and not chk[next_y][next_x]:
                chk[next_y][next_x] = True
                q.append((next_y, next_x, cnt+1))

print(bfs(0,0))

##################################################################################################
#########시간초과 코드#########


import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())

dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)

miro = [input() for _ in range(n)]
    
def is_valid_coord(y, x):
    return 0 <= y < n and 0 <= x < m and miro[y][x] == '1'

chk = [[False] * m for _ in range(n)]


def bfs(start_y, start_x):
    q = deque()
    cnt = 1
    q.append((start_y, start_x, cnt))

    while q:
        y, x, cnt = q.popleft()
        if y == n - 1 and x == m - 1:
            return cnt
        chk[y][x] = True
        for k in range(4):
            next_y = y + dy[k]
            next_x = x + dx[k]
            if is_valid_coord(next_y, next_x) and not chk[next_y][next_x]:
                q.append((next_y, next_x, cnt+1))

print(bfs(0,0))

djm03178 1년 전 1

후자는 여러 정점이 하나의 정점을 동시에 방문하려고 할 때 그 정점이 여러 번 큐에 들어가는 문제가 생깁니다. 그러면 그 정점이 큐에서 여러 번 나와서 주변에 있는 정점을 또 여러 번 큐에 넣고, 그것들이 또 나와서 주변에 있는 점을 여러 번 큐에 넣고... 하는 것이 중복되어 겹치면서 기하급수적으로 큐에 많이 삽입하게 됩니다.

hyong11 1년 전 0

와 이해됐습니다... 큐가 선입선출이라는 걸 인지 못하고있었네요,, 답변주신대로 pop될 때 체크리스트를 true해주면삽질 엄청하겠습니다 ㅠㅠ

감사합니다!!

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

문제

문제

출처

ICPC

여러번 수정해봤지만 계속 시간초과가 나옵니다 ㅠ 문제가 뭘까요...

hyong11 1년 전 0

eatingnut 1년 전 1

hyong11 1년 전 0

djm03178 1년 전 1

hyong11 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말