feel321   2년 전

index 0은 사용하지 않고 첫번째가 index1처럼 사용했습니다.

DFS로 푼것은 성공했는데요

BFS로 푸니까 오히려 시간초과가 납니다.

25%에서 잠시 주춤거리다가 시간초과가 나는데

BFS 어느 부분이 이상하게 되어 있는지 조언해주실 수 있으실까요?

feel321   2년 전

원래 fs로 읽어오는 방식을 사용했었는데요

fs로 읽기 + DFS 는 문제없었고

fs로 읽기 + 위 BFS코드는 그냥 시간초과가 났습니다.

뭐라도 해보려고 realine으로 바꾸니까 25%에서 주춤거리다가 시간초과 나는식으로 바뀐 상태입니다.

wizardrabbit   2년 전

안녕하세요! 코드에서 아래와 같이 수정하니 시간초과가 해결되었습니다.

▶ 38번째 줄의 코드 제거
▶ 53번째 줄 바로 아래에, if (ground[newY][newX] === 0) continue; 추가

제가 확인한 결과 현재 코드의 시간 초과 원인은 이렇게 추측하고 있습니다:

1) 새로운 좌표를 큐에 넣는 작업은 60번째 줄에서 일어납니다.

2) 그런데 60번째 줄에서 원소를 추가할 때 바로 값을 0으로 바꾸지 않으므로 여러 좌표에서 같은 좌표를 큐에 넣을 수 있습니다. 예를 들어 (2, 2) 좌표는 (1, 2), (2, 1), (3, 2), (2, 3) 좌표에서 접근할 수 있으니 (2, 2)는 큐에 최대 네 번이나 들어갈 수 있게 됩니다.

3) 그리고 큐에 들어간 같은 좌표에 대한 작업이 여러 번 실행됩니다. 즉 작업이 비효율적이게 됩니다. 코드에서는 큐에서 좌표를 빼냈을 때 이미 좌표의 값이 0 (= 이미 처리된 원소) 임에도 작업을 동일하게 수행합니다.

4) 3)의 작업이 연쇄적으로 일어나며, 필요없는 같은 작업이 여러 번 반복되면서 시간 초과를 유발하게 됩니다.

그래서 저는 같은 좌표에 대한 불필요한 작업이 반복되는 것을 막기 위해 간단하게 큐에서 원소를 빼냈을 때 이미 좌표의 값이 0이면 바로 작업을 건너뛰는 방식으로 시간 초과를 해결했습니다. 큐에 좌표를 넣을 때(60번째 줄) 바로 값을 0으로 바꿔버려서 다른 원소들이 접근을 하지 못 하게 하는 것도 방법입니다.

설명이 좀 난해해졌지만, 이해가 되었으면 좋겠습니다.

feel321   2년 전

@wizardrabbit

선생님 감사합니다.

말씀해주신 내용을 통해서 제가 큐 처리를 잘못하고 있는것을 알았습니다.

BFS를 다시 공부했고, 싹 지우고 다시해서 성공 판정을 받았습니다.

불필요한 작업을 줄이도록 조건문 continue 처리를 더 꼼꼼히 하겠습니다.

creeperss85   2년 전

왜 C++ BFS로 하면 메모리 초과가 나버리는건지 했는데... 감사합니다 선생님

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