-
[BOJ - 16946] 벽 부수고 이동하기 4백준알고리즘 2020. 2. 27. 00:14
https://www.acmicpc.net/problem/16946
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
www.acmicpc.net
이 문제에 대한 가장 간단하고 전형적인 완전탐색 방법은 모든 벽에서 모든 빈공간을 탐색해나가는 것이라고 생각했다.
하지만, 최대 벽의 개수가 1000x1000개인 100만개정도의 숫자가되는데, 이러한 100만개의 탐색뿐아니라, 탐색한 뒤
방문지 초기화를 해주는 과정까지 고려하면 시간초과가 날것이고, 1000x1000x1000의 int 배열을 사용해야 하는경우에는
메모리 초과가 나는것이 매우 자명했다.
따라서 방법을 바꾼것이, 모든 빈공간을 탐색하고, 그 각각의 영역(빈공간으로 인접되어있는 영역)에 대한 영역 값과
빈공간의 크기를 배열에 저장한과정을 거치고, 벽에서의 사방으로 값들을 합쳐나가 해답을 구할수있다.
'백준알고리즘' 카테고리의 다른 글
[BOJ - 12886] 돌 그룹 (0) 2020.02.27 [BOJ - 16933] 벽 부수고 이동하기3 (0) 2020.02.27 [BOJ - 14500] 테트로미노 (0) 2020.02.24 [BOJ - 18429] 근손실 (0) 2020.02.14 [BOJ - 4217] 신성 문자 (0) 2020.02.14