Softeer Lv3 - 나무섭지

문제

https://softeer.ai/practice/7726

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

풀이 시간 : 6시간

시도 횟수 : 9

복기

정답률에 비해 문제가 쉽다고 생각했지만, 정작 6시간정도 풀었다. 풀이 접근법을 순서대로 적어봤다.

 

1. 남우의 출구 까지 최단거리 길 저장 + 유령이 잡을수 있는지 판단

 

(x, y) 좌표로 이루어진 남우의 최단 거리 길들을 저장한다.

남우의 최단거리 길들 중 유령에게 잡히지 않는 길이 하나라도 있다면 탈출로 간주한다.

유령에게 잡히는 조건은 남우의 x,y 좌표와 유령의 x,y 좌표의 맨해튼 거리를 계산하여, 남우의 걸어온 길이보다 유령이 짧으면 잡힌것이다.

 

그 결과 시간 초과가 났다.

 

2. 반복문으로 각 좌표별로 유령이 갈 수 있는 최단거리 계산 + 남우 출구 까지 최단거리 찾기

 

최단거리 길을 찾고, 유령의 멘해튼 거리를 계속 계산해줄 필요가 없었다. 왜냐하면 유령의 맨해튼 거리는 항상 동일하니깐.

그래서 반복문으로 유령이 각 좌표별로 갈수있는 최단거리를 맨해튼 계산으로 먼저 계산하여 저장한 뒤,

남우가 최단거리 찾을때, 못넘어가는 조건은 벽이거나, 유령이 먼저 도착하는 경우를 고려하여 최단거리 찾기로 풀이했따.

 

그 결과 시간초과 났다.

 

3. BFS로 각 좌표별로 유령이 갈 수 있는 최단거리 계산 + 남우 출구 까지 최단거리 찾기

 

격자의 최대 크기는 10^3* 10^3 이다. 그렇다면 최대 유령의 수는 10^6 이다.

반복문으로 맨해튼 거리를 계산했을때 시간 복잡도를 계산하면

10^3 * 10^3 * 10^6 으로 시간 제약조건을 아득히 넘어선다.

 

결국 좌표별로 유령이 갈 수 있는 최단거리를 계산하면 되기 때문에 BFS 로 계산해줬고 통과할 수 있었다.

 

 

 

문제 풀이 방법을 생각할때, 시간 복잡도를 먼저 생각했다면, 좀 더 빠르게 반복문으로 유령의 최단거리를 맨해튼 거리로 계산하지 않고 풀수 있었을거같다.

더 나은 풀이 방법