하루가 지날 때마다 dfs를 돌리면

운 안 좋으면 시간초과 날지도 모르겠네요. 호출 횟수를 줄여보세요.

(1) d일 째에 백조가 서로 만나지 못했는데, d-1일 째에는 백조가 만날 수 있을까?

당연히 없을 겁니다.

그런 관점에서 보면 이분으로 접근은 가능하죠.

이 경우에 시간 복잡도를 대략적으로 계산을 해 보세요. 어느 정도 나올지.. 최악의 경우에 어느 정도가 나올지..

다른 풀이는 조금만 더 고민해 보세요.

참고로 유니온 파인드로 푸는 방법도 있긴 하지만..

그건 솔직하게 말해서 구현 능력이 안되면 이분보다는 훨씬 어려우실 거에요. 

네.. 제가 그 방법으로 오늘 밤새고도 못 풀었습니다. 누가 쉽게 구현할 수 있는 조언 좀 주세요.. 제 능력이 여기까지네요.

메모리 초기화 안 하고 빙산 정보를 미리 전처리 해 놓고

bfs를 돌리니 496ms로 아슬아슬하게 통과하네요.

이게 가능한 이유는

멤 초기화 안 하면

최악의 경우 2*floor(밑이 2인 log1500)*1500*1500 즈음 되기 때문이죠. 이게 대충 5000만 즈음 나오니 500ms가 나오고요.

돌 때마다 visit 배열 초기화하고

이분 탐색 하실 때 빙산도 다시 build 하시면 여기에 3에서 4정도가 곱해집니다. 그러면 TLE가 나는 거죠.

원하시면 이런 류의 이분 탐색 문제들도 링크 걸어놓을게요.

빙산이 몇 일째에 녹는지 미리 전처리를 하는 겁니다.

예를 들자면..

빙산을 B 바다를 W라고 합시다.

그러면..

BWWW

BBWW

BBWW

BBWW

라는 맵이 있을 때

1 0 0 0

2 1 0 0

2 1 0 0

2 1 0 0

이런 식으로 전처리를 하실 수 있습니다. 그런 경우에는 만약에 d일차일 때

빙산이 녹는 시점이 d보다 크다면 가면 안 된다는 것을 알 수 있지요.

bfs 같은 경우 보통은 하실 때마다 visit 배열을 memset 같은 걸로 초기화 하시는데요.

그거 대신에 몇 번 bfs를 수행했지? 라는 변수를 저장해서 하면 초기화를 안 해도 되고요.

예를 들자면.. 1번째 bfs를 수행할 때, 방문한 지점을 1로 표시했다면

2번째 bfs를 수행할 때에는 2로 표기하고

3번째 bfs를 수행할 때에는 3으로 표기하고..

보통 이렇게 맵이 엄청나게 큰 경우에는 유니온 파인드를 이용합니다만..

전 솔직히 그것까지 못 쓰겠고요.. 오늘 새벽에 그렇게 풀다가 포기했습니다..

그리고 그것을 모른다고 못 풀면 손해잖아요..

그럴 때는 이분탐색도 종종 쓰입니다. 이분탐색이라는 게

이거 이상일 때는 조건을 만족하느냐? 안 만족하느냐? 를 따져주는 건데요..

백조의 호수 문제 같은 경우에도 d일 째에 만나지 못했는데 d-1일 째에는 만날 리가 없으니 역시 이분탐색으로 쪼개버릴 수 있지요.

bfs를 돌릴 때에는 2개가 중요하잖아요.

1. 갈 수 있는가?

2. 이미 방문했는가?

보통은 갈 수 있는가? 는 맵에서 0 또는 1로 처리를 많이 하시고요.

이미 방문했는가? 는 visit 배열에서 1로 보통은 하십니다. 그렇기에, bfs를 다시 재수행 하실 때마다 0으로 memset을 해버려야 하죠.

이 관점을 뒤집으시면 됩니다.

갈 수 있는가? 를 빙산이 d일차에는 녹았는가? 로. (이건 빙산이 몇 일 째에 녹는지를 전처리 하시면 바로 아실 수 있고요.)

이미 방문했는가? 는 bfs를 다시 수행할 때 마다 특정한 값으로 채워졌는가? 로 바꾸시면 됩니다.

이 두 질문에 대해서, 관점을 바꾸지 않으면 이분으로 접근했을 때 TLE가 나오더라고요.

많이 푸시면 익숙해지실거에요.

@chogahui05 설명 감사합니다!

@chogahui05 새로운 관점 감사합니다 혹시 이런 류 이분 탐색 문제 더 알 수 있을까요??