[백준] 17090 미로 탈출하기 (파이썬,python)

https://www.acmicpc.net/problem/17090

17090번: 미로 탈출하기

24/02/09 현재 난이도: 골드3

쓰이는 알고리즘: 다이나믹 프로그래밍(dp), 그래프탐색

내가 생각하는 난이도: 골드3

남의 도움을 받았는가?: X

 

 

들어가기전에 서론

 

이 문제는 ICPC신촌에서 교육을 받고 1시간 동안 랜덤디펜스를 진행하였는데..

 

나는 B번 C번 (실버1, 골드5) 문제를 풀었고 이 문제는 D번 문제로 나왔다.

이 문제를 건드려보고 싶었으나 C번 문제에서 실패를 너무 많이했고

B번 문제가 기하문제였는데 기하를 평소에 풀지않으니 실버문제도 버벅거려버렸다 ㅠㅜ

 

그래서 이 문제를 건드리지 못 했고 집에 도착해서 다시 문제를 풀어봤는데 금방 풀렸다.

차라리 B번말고 이 문제를 풀 걸 그랬다 ㅠ

 

이 문제는 DP와 BFS로 해결할 수 있다.

 

이제 본론으로 들어가서 이 문제를 어떻게 푸는지 이야기해보겠다.

 

 

이 문제를 처음 봤을때 드는생각이 (r,c) 가 r이 x좌표고 c가 y좌표인가? 라는 생각을 했는데

생각해보니 r은 row의 약자이고 c 는 column의 약자가 아닌가 따라서 r이 y좌표고 c가 x 좌표이다.

조금 혼란이 올 수 있게 문제가 써진거라고 생각한다 ㅋㅋ..

 

내가 짠 알고리즘은 dp를 dp=[[False for _ in range(M)] for _ in range(N)] 로 선언하고 

그래프의 모든 점을 다 돌긴 하는데 그 점에서 만약 탈출을 성공한다면

 

그 갔던 경로들은 다시 돌아보지 않고 dp에 그 경로들을 전부 된다는것을 저장해준다.

 

그리고 마지막에 dp에서 True의 개수를 세서 답을 구해준다.

 

이제 코드를 부분적으로 살펴보자

 

 

 

 

그래프를 입력받고 dp를 선언해준다

이후 (y,x)를 모두 돌면서

만약 dp[y][x]를 방문처리(True) 해주지 않았으면 코드를 진행해준다

그 (y,x)를 q에 넣고 돌면서 경로를 s2라는 집합에 저장해준다

nowy,nowx 는 q에서 뽑은 현재위치이다.

만약에 graph[nowy][nowx] 가 U라면 nowy 를 1을 빼준다

그리고 (nowy,nowx)가 s2에 있다면 사이클을 돌고 있는것이므로 무한루프를 돌게 될것이다

따라서 s2에 있다면 그대로 while문을 break해준다 없다면 사이클을 돌고있는것이 아니므로

코드를 진행해준다.

 

만약 nowy를 1을 뺀것이 0 과 N-1 사이에 있다면 미로를 탈출한 것이 아니므로

s2에 (nowy,nowx)를 넣어주고 q에도 (nowy,nowx)를 넣어줘 계속해서 돌게한다.

 

만약 nowy에서 1을 뺀것이 0과 N-1 사이에 없다면 미로를 탈출한 것이므로,

s2에 있는 지나온 경로들의 dp를 모두 True로 만들어준다.

 

또한 dp[nowy][nowx]가 True라면 굳이 다음길을 가보지 않더라도 True일것이므로

그동안 걸어왔던 경로들만 dp에 True로 업데이트 해준다

 

 

 

 

 

같은 과정을 R,D,L에 대하여 반복해주면 된다.

 

 

 

그리고 마지막으로 구하고자하는 dap을 설정해주고

 

dp를 돌면서 True라면 dap을 1을 더해줘 dap을 구해주면 된다.

 

문제풀이는 여기까지이다.

 

 

 

마지막으로 잡담을 좀 하자면

 

 

사실 이 문제도 집에와서 한 번에 성공하지 못했다.. 구현하면서 코드의 실수가 있었기 때문이다

 

첫 번째 실수는 인덱스 에러인데 nowx의 범위를 M보다 작을 때인데N보다 작다로 해줘버렸다.

이렇게 해도 답이 똑같이나오는 테스트케이스들이어서 실수를 걸러내지 못했다...

(테케 탓이라기 보다는 제 탓이기는 함...)

두번째는 91퍼정도까지 올라가길래 맞는 줄 알았다.

미세하게 시간초과가 뜬것이다. 그래서 어떻게 해야 시간을 줄일 수 있을까 고민하다가

 

 

처음에는 and not dp[nowy][nowx] 를  써주지 않았었다.

길을 가다가 어느 길이 dp에서 True라는것을 알게되면 그 다음길은 걸어볼 필요없이

그냥 다 맞기 때문에 굳이 다 걸어보지 않아도 된다.

사실 처음 짤 때 이걸 생각안한건 아니었는데 안해도 딱히 시간이 많이 차이안나지 않을까?

하고 좀 피곤하기도 하여 그냥 가줬다.

그래서 시간초과가 뜨자마자 와서 이 코드를 써줬다

 

잔 실수가 너무 많은 것같다... 열심히 줄여보자 !!!