목록달이차오른다가자 (1)
Hello Ocean! 🌼
[백준/C++] 1194. 달이 차오른다, 가자
문제 https://www.acmicpc.net/problem/1194 0에서 출발하여 1까지 갈 수 있는 최단경로를 구하는 문제이다. #은 지나갈 수 없고, a~f는 열쇠, A~F는 문이며 각 문을 지나기 위해서는 해당하는 소문자 열쇠를 가지고 있어야한다. 풀이 열쇠와 문이라는 요소가 추가되기는 했지만, 기본적으로는 BFS를 이용하여 최단경로를 찾는 문제이다. 구조체를 만들어서 BFS를 돌리는것 까지는 비교적으로 금방 할 수 있었는데, 메모리초과가 났다. visited배열을 visited[2][2][2][2][2][2][51][51]로 만들고, 구조체에 6칸짜리 vector를 넣어서 그런 것 같았다. 검색을 해보니, 열쇠 관련 부분을 "비트마스킹"으로 해결해야 하는 문제였다. 따라서 visited배열을..
Algorithm
2021. 6. 2. 21:49