[BOJ C++] 벽 부수고 이동하기 4

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

16946번: 벽 부수고 이동하기 4

 

 

문제 이해

벽과 길로 이루어진 공간이 주어지고 벽을 허물었을 때 해당 지점에서 갈 수 있는 공간들의 크기를 구하는 문제였습니다.

 

 

입출력 조건

시간 제한은 2초, 공간의 크기는 최대 1,000x1,000 이였습니다.

 

 

풀이

처음에는 단순하게 벽인 지점마다 그냥 bfs 돌리면 되겠다 라는 생각을 했습니다.

그리고 그렇게 짰더니 시간초과가 떴습니다..1000x1000x1000을 하면 약 10억이 나오더군요

시간초과가 날만 한가..? 라는 생각이 들었습니다..

그래서 메모이제이션을 생각했습니다.

우선 0인 공간들을 먼저 탐색해서 해당 공간이 몇칸이지 확인하고, 이후에 1에서 bfs를 돌때 해당 이미 몇칸이 이어붙어있는 것인지 알고 있는 벽을 만나게 되면 queue에 넣지 않고 바로 더하면 되는 것이였습니다.

그렇게 풀었더니 중간 중간 시행착오는 많았지만 어찌어찌 해결할 수 있었습니다.

 

 

에러 및 느낀 점

시간을 많이 단축했다 생각을 했음에도 쓷레없이 visit를 처리하거나 이를 초기화 해주는 것에 시간을 많이 써서 시간초과가 여러번 더 났었습니다.

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/16946_%EB%B2%BD%20%EB%B6%80%EC%88%98%EA%B3%A0%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0%204.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.