728x90
링크
https://www.acmicpc.net/problem/2589
난이도(solved.ac 참고)
골드5
풀이
n과 m이 각각 50까지밖에 안되는 것을 보고 브루트포스로 해도 되겠다는 생각이 들었다. 우선 아이디어는 각 위치별로 가장 먼 곳까지 가는 숫자를 찾아야 하기 때문에 L일 때마다 BFS를 실행하고 이중 배열을 초기화하여 최대값을 갱신해가는 것인데, 일반적인 BFS로만 풀면 PyPy3으로만 통과할 수 있다.
코드에도 있듯이, 좌우 혹은 상하가 모두 L이라면 그 자리는 가장자리가 아니기 때문에 탐색을 넘김으로써 불필요한 배열 재선언 및 BFS의 실행을 방지할 수 있다.
'CS > 알고리즘' 카테고리의 다른 글
| [Python] BOJ(백준) 1294번 - 문자열 장식 (0) | 2022.02.21 |
|---|---|
| [Python] BOJ(백준) 16496번 - 큰 수 만들기 (0) | 2022.02.20 |
| [Python] BOJ(백준) 15591번 - MooTube (Silver) (0) | 2022.01.28 |
| [Python] BOJ(백준) 15655번 - N과 M(6) (0) | 2022.01.15 |
| [Python] BOJ(백준) 13702번 - 이상한 술집 (0) | 2022.01.12 |
