dlssrb7777   5년 전

아래는 제가 도움받았던 반례 두 가지 입니다.

4 10

1 1 1 2

1 2 1 3

1 2 4 1

1 3 1 4

1 3 3 1

1 4 2 4

1 4 2 1

2 1 4 4

3 1 4 3

4 1 3 4

11

4 10
1 1 1 2
1 2 4 1
1 2 1 3
1 3 3 1
1 3 1 4
1 4 2 4
1 4 2 1
2 1 4 4
3 1 4 3
4 1 3 4
11

저에겐 나름 어려운 문제였기에 풀고나서 복기해봤습니다. 저의 경우 오답 -> 시간 초과 -> 오답 -> 정답이었고, 그 코드와 과정을 정리할 겸 공유합니다.

첫 오답은 아예 잘못 생각했고, 두 번째 오답의 경우 구현에 있어 논리적으로 실수한 부분입니다. 시간초과를 해결한 방법이 핵심 Key였다고 생각합니다.

첫 오답 코드 : https://www.acmicpc.net/source...

시간 초과 코드 : https://www.acmicpc.net/source...

두번째 오답 코드 : https://www.acmicpc.net/source...

첫 오답의 경우 위의 반례에서 걸러졌습니다. 첫 코드의 결정적인 패인은 스위치를 한 번만 둘러 봤기 때문입니다. 즉, 처음 스위치로 불을 키고 바로 방에 갈 수 있는 지 확인한 다음, 못가면 바로 버리도록 했습니다. 후에 다시 방에 갈 수 있게 될 수도 있기 때문에 버리면 안됩니다.

시간초과의 경우 핵심은 '이 방은 갈 수있는 방인가'를 확인하는 방법입니다. 이전에 저는 0,0부터 일일이 bfs돌려서 확인했었습니다. O(1)로 확인할 수 있는 방법을 생각해보시면 될 것 같습니다.

============밑에부터는 강력한 정답스포가 될 것 같아요================

두 번째 오답의 경우 정답코드와의 핵심적인 차이는 '갈 수 있는 방을 업데이트하는 타이밍'입니다. 핵심은 덱(불이 켜졌지만 이전에는 갈 수 없었던 방들)을 탐색하기 전에 새로 불이 켜진 방을 통해 새롭게 갈 수 있는 방을 업데이트 해주는 것입니다. 놓치기 쉽지만 중요한 부분인 것 같습니다. 여러모로 도움되셨으면 좋겠습니다 :) 

 

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