다를 수 있습니다. 똑같은 게임을 돌려도 어떤 때는 렉이 걸리고 어떤 때는 안 걸리는 것과 비슷한 이유입니다.

제가 bfs 문제를 풀면서 시간초과로 인해 답이 틀린경우가 몇번 잇었는데  이 때도 같은 이유로 그럴수도 있나요 ? 

가능은 합니다. 하지만 대부분의 문제의 경우 의도한 시간복잡도의 코드를 짜면 제한 시간의 1/5 내에는 통과가 되게 만들기 때문에 그 차이로 통과가 되고 못 되고가 갈리는 경우는 거의 없습니다. 시간복잡도가 의도된 풀이를 넘어서면 대체로 제한 시간의 몇 배 이상이 걸리기 때문에 약간의 오차가 발생하는 것으로는 아무리 많이 시도해도 통과하기 어려운 경우가 대부분입니다.