알고리즘/구현
-
BOJ 10875 뱀알고리즘/구현 2022. 7. 25. 10:49
https://www.acmicpc.net/problem/10875 10875번: 뱀 가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 www.acmicpc.net 문제는 단순하다. 지나온 정점을 다시 지나가려 하거나, 격자판 밖으로 나가면 죽는다!! 그런데.. 격자판의 크기가.. 2억 * 2억 이다. vis배열을 당연히 사용할 수 없다. 나의 굳어버린 머리는 vis배열 없이는 도저히 해결할 수 없을 것 같았다.. 지나간 곳만 저장하는 sparse table을 이용해볼까 했는데.. 모든 정점을 지나가면?? 결국 vis배열을 사용한 것과 같아서..