2468. 안전지대

풀이

실패 → 시간 초과

def safe(h):            # h: 가준 물 높이 /    que = deque()  
	# 부분 1
	que = deque()
    visited = [[0 for _ in range(N)] for _ in range(N)]  
	# 부분 2
    while True:  
        nextSafe = findNextSafe(h,visited)  
        if nextSafe:  
            visited[nextSafe[0]][nextSafe[1]] = 1  
            que.append(nextSafe)  
        else: return  
		  # 부분 3
        while que:  
            node = que.popleft()  
            x = node[0]  
            y = node[1]  
            for i in a:  
                nx = x+i[0]  
                ny = y+i[1]  
                if 0<=nx<N and 0<=ny<N and visited[nx][ny] == 0 and lst[nx][ny] > h:  
                    visited[nx][ny] = 1  
                    que.append((nx,ny))  
  
  
  
def findNextSafe(h, visited):  
    for i in range(0, N):  
        for j in range(0, N):  
            if visited[i][j] == 0 and lst[i][j] > h:  
                waterCnt[h] += 1  
                return (i, j)  
  
    return None  
  
  
  
input = __import__('sys').stdin.readline  
N = int(input())  
a = [[-1, 0], [1, 0], [0, -1], [0, 1]]  
lst = [list(map(int, input().split(" "))) for _ in range(N)]  
waterCnt = [-1]*101  
  
# 물 높이  
waterCnt[0] = 1  
waterCnt[100] = 0  
 
for i in range(N):  
    for j in range(N):  
        h = lst[i][j]  
        if waterCnt[h] == -1:  
            waterCnt[h] += 1  
            safe(h)  
safe(100)  
print(max(waterCnt))

용어
- 안전한 땅: 특정 물높이 h에 대해 h를 초과하는 지역
- 안전지대: 연결되어있는 안전한 땅을 안전지대라고 부름 (연결된 것중 최대 크기)
전역변수
- waterCnt 배열: 각 물높이에 대해 안전지대가 몇 개인지 개수를 저장
- a 배열: 연결된 다음 안전지대를 찾을 때, 좌표 이동을 위한 배열
- lst 배열: 땅 높이에 대한 정보가 저장
findNextSafe(h, visited)의 역할: 안전한 땅을 탐색하다가 길이 끊겼을 경우(혹은 최초에), 다음으로 아직 방문하지 않은 안전한 땅을 찾는 역할
- 배열 전체 (땅 전체)를 순회하면서, 아직 방문하지 않았고, 안전한 땅을 찾으면, 해당 땅 위치를 return
  - 또한 이 경우 새로운 안전한 땅 유닛 (=안전지대)의 시작이기 때문에, 해당 높이의 안전지대 count를 올려줌 (waterCnt[h])
  - 찾는 값이 없을 경우 None을 return
safe(h)의 역할: 특정 물높이 h에 대해 h를 초과하는 지역(=안전한 땅)을 방문하고 그 지역과 연결된 다른 안전한 땅을 차례로 방문하는 함수
- 부분 1:
  - visited 배열: 해당 물높이 h에 대해서 탐색할 때, 특정 지역에 방문 했는지를 체크하는 용도의 배열
  - que: 선입 선출의 특징을 가진 리스트로, 갈 수 있는 땅을 발견했을 때, 해당 que에 집어 넣음. 또한 순서대로 빼면서, 빼낸 땅에 대해 인접한 안전한 땅이 또 있는지 확인하기 위해 선언
- 부분 2
  - findNextSafe함수를 통해 다음 안전지대 시작점을 찾을 수 없을 때까지 계속 안전지대 탐색을 반복
- 부분 3
  - 방문한 땅을 하나 빼냄 → node = que.popleft()
  - 해당 땅에 인접한 땅들을 순회((x-1, y), (x+1, y), (x, y-1), (x, y+1))
  - 그 땅이 배열의 안에 있고(0<=nx<N and 0<=ny<N), 안전한 땅이며(lst[nx][ny] > h), 아직 방문하지 않은 곳(visited[nx][ny] == 0)인지를 체크
  - 모두 True라면 해당 땅을 방문하고, 다음 탐색을 위해 que에 삽입
  - 이것을 que가 다 빌 때까지 반복
물 높이(h) 관련
- h = 0일 때, 안전지대는 1개 → 모든 땅이 물에 잠기지 않았음
- h = 100 일때, 안전지대는 0개 → 모든 땅이 물에 잠겼음
- 이 외에 물높이에 따라 안전지대의 개수가 변하기 위해서는, 물높이가 특정 땅의 높이와 일치되어야한다.
- 즉, 땅 높이가 1 5 8일 때, 물높이 1에서 부터 4까지는 동일한 땅이 물에 잠기고 동일한 땅이 물위에 있지만, 5부터는 물에 잠긴 모습이 변하게 됨.
- 따라서, 탐색에 적용할 h의 값은 모든 땅의 높이와 최소 높이 0, 최고 높이 100이다.
출력: waterCnt의 최대값을 출력
시간 초과 원인:
- 다음 안전지대 시작 위치를 찾는걸 어떻게 해야하지 헷갈렸는데, 어김없이 거기서 문제가 생김
- findNextSafe 함수에서 다음 안전지대 시작점을 찾을 때, 매번 처음부터 끝까지 탐색을 하니까 시간이 오래걸림
- 함수 findNextSafe와 safe로 나누지 말고 2중 포문 돌리면서 다음 시작위치를 탐색하다가 시작위치를 찾으면 que에 넣어서 안전지대 하나 탐험 시작.
- 그리고 탐험 끝나면, 아까 찾은 안전지대 시작위치 뒤부터 탐색을 시작해서 다음 안전지대를 찾는 방식으로 수정

성공

from collections import deque  
  
def safe(h):            # h: 가준 물 높이 /    que = deque()  
    visited = [[0 for _ in range(N)] for _ in range(N)]  
    for i in range(0, N):  
        for j in range(0, N):  
            if visited[i][j] == 0 and lst[i][j] > h:  
                waterCnt[h] += 1  
                visited[i][j] = 1  
                que.append((i,j))  
  
                while que:  
                    node = que.popleft()  
                    x = node[0]  
                    y = node[1]  
                    for a in A:  
                        nx = x+a[0]  
                        ny = y+a[1]  
                        if 0<=nx<N and 0<=ny<N and visited[nx][ny] == 0 and lst[nx][ny] > h:  
                            visited[nx][ny] = 1  
                            que.append((nx,ny))  
  
  
input = __import__('sys').stdin.readline  
N = int(input())  
A = [[-1, 0], [1, 0], [0, -1], [0, 1]]  
lst = [list(map(int, input().split(" "))) for _ in range(N)]  
waterCnt = [-1]*101  
  
  
waterCnt[0] = 1  
waterCnt[100] = 0  
  
for i in range(N):  
    for j in range(N):  
        h = lst[i][j]  
        if waterCnt[h] == -1:  
            waterCnt[h] += 1  
            safe(h)  
safe(100)  
print(max(waterCnt))

Computer #PS

☀️ Log

풀이

실패 → 시간 초과

성공

탐색기