반응형
16946
-
BOJ) 벽 부수고 이동하기 4알고리즘/백준 2020. 7. 3. 16:37
벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 풀이 처음에는 모든 벽에 대해서 벽을 허물고 값을 구하고자 했다. 하지만, 주어진 n과 m의 최대값이 1000이나 되기 때문에 시간초과가 뜰 것 같았다. 그래서 생각한 것은 0에 대해서 grouping을 해주는 것이다. 빈칸이 이어진 곳들에 대해서 그룹 index를 남기고, 몇 개의 빈칸이 존재하는지 세주어서 저장하는 것이다. 이후에, Map을 돌면서 벽을 허물었을 경우, 상하좌우에 (인접한 곳에) 빈칸 그룹이 가지..