2206번 - 벽 부수고 이동하기
1달전에 맞췄던 문제였는데 최근에 확인해보니 시간초과로 재채점되어있더라구요.
1달전 맞았다가 재채점 되어 시간초과로 채점된 코드 : https://www.acmicpc.net/source...
방금 푼 코드는 아래에 추가했습니다.
핵심은 최단거리로 도착하고 바로 함수 종료하느냐의 차이인것 같긴합니다. 1달전은 어거지로 짜서 저도 잘 못읽겠는데, 방금 푼 코드는 그래도 최소한의 가독성은 유지하려 노력했습니다(주석도 썼구요 ㅠㅠ).
1달전 코드는 어떻게 통과되었는지 잘모르겠네요..
1달전 코드의 시간 복잡도는 대략 (벽의 갯수) x (BFS 돌게되는 칸의 갯수) 인 것 같습니다.
1000 x 1000 입력이고, 벽의 갯수가 N이라 할때 N x (1000 - N) x (1000 - N) 정도 인 것 같습니다.
코드 참고하실분 참고하시고, 혹시 제 분석중에 틀린 부분이 있다면 정정 부탁드리겠습니다 :)
저거 근데 어차피 못맞춘사람은 링크 들어가도 404뜨긴합니다.
넣으실꺼면 글에다가 넣으셔야할꺼에요.
@nahwasa 감사합니다 글 수정했습니다.
댓글을 작성하려면 로그인해야 합니다.
dlssrb7777 5년 전
1달전에 맞췄던 문제였는데 최근에 확인해보니 시간초과로 재채점되어있더라구요.
1달전 맞았다가 재채점 되어 시간초과로 채점된 코드 : https://www.acmicpc.net/source...
방금 푼 코드는 아래에 추가했습니다.
핵심은 최단거리로 도착하고 바로 함수 종료하느냐의 차이인것 같긴합니다. 1달전은 어거지로 짜서 저도 잘 못읽겠는데, 방금 푼 코드는 그래도 최소한의 가독성은 유지하려 노력했습니다(주석도 썼구요 ㅠㅠ).
1달전 코드는 어떻게 통과되었는지 잘모르겠네요..
1달전 코드의 시간 복잡도는 대략 (벽의 갯수) x (BFS 돌게되는 칸의 갯수) 인 것 같습니다.
1000 x 1000 입력이고, 벽의 갯수가 N이라 할때 N x (1000 - N) x (1000 - N) 정도 인 것 같습니다.
코드 참고하실분 참고하시고, 혹시 제 분석중에 틀린 부분이 있다면 정정 부탁드리겠습니다 :)