모래성
-
[백준]10711: 모래성 - JAVA문제풀이/백준 2021. 7. 2. 15:56
[백준]10711: 모래성 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 풀이 이 문제는! 직관적인 방법으로 생각해서 풀면 시간초과가 발생하는 문제이다. 우선, 대부분 첫번째로 떠오른 풀이 방법은 다음과 같을 것이다. 모든 노드의 탐색을 반복하며 모래성이 있는 노드 주변의 8방향 노드값을 확인하여 무너지는지, 무너지지 않는지 확인한다. 위의 방법으로 푼다면 테스트 코드는 통과되겠지만 시간 복잡도 측면에서 효율적이지 못하다. 매번 모든 노드를 탐색하는 방법 보다 더 효율적인 탐색 방..