코딩테스트/파이썬
[백준/2468/파이썬] 안전 영역 (Python, dfs)
JI NY
2023. 3. 17. 22:42
[백준/2468/파이썬] 안전 영역 (Python, dfs)
코드 1 (함수 x)
from sys import stdin,setrecursionlimit
import copy # 복사
input = stdin.readline
# 변수 정의
depth_arr = [] # 입력 깊이 배열
depth_arr2 = [] # 비교할 입력 길이
safe_arr = [] # 안전지대 개수
depth_max = 0 # 최대 깊이
depth = 4
# 입력
N = int(input())
#재귀 깊이 늘리기
setrecursionlimit(N*N+10)
# array 추가
for i in range(N):
depth_arr.append(list(map(int, input().split())))
depth_max = max(depth_arr[i]) # 최대 깊이 구하기
def dfs(x,y): #(행, 열)
#주어진 범위를 벗어나는 경우에는 늑시 종료
if x <= -1 or x >= N or y<= -1 or y>= N:
return False
if depth_arr2[x][y] == 0: #만약 방문하지 않았다면, ==0
# 해당 노드 방문 처리
depth_arr2[x][y] = 1
#상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x-1, y) # 상 (행-1, 열)
dfs(x, y-1) # 좌 (행, 열-1)
dfs(x+1, y) # 하 (행+1, 열)
dfs(x, y+1) # 우 (행, 열+1)
return True
return False # 만약, 이미 방문했다면 False
for k in range(0, depth_max+1): #1~ depth_max까지
# depth만큼 진행 ( 이건 나중에)
depth_arr2 = copy.deepcopy(depth_arr) # 리스트 복사
#depth 이하이면, 1로배열 넣기
for i in range(N):
for j in range(N):
if(depth_arr[i][j] <= k ): # 만약 높이가 장마 depth이하라면,
depth_arr2[i][j] = 1 # 물에 잠겼다
else:
depth_arr2[i][j] = 0 # 물에 잠기지 않았다.
# print(depth_max)
# print(depth_arr)
# print(depth_arr2)
# 노드 전체 방문
count = 0
for i in range(N):
for j in range(N):
if dfs(i,j) == True: # 새로 방문했다면
count+= 1 # count++
safe_arr.append(count)
print(max(safe_arr))코드2 (함수1)
from sys import stdin,setrecursionlimit
import copy # 복사
input = stdin.readline
# 변수 정의
depth_arr = [] # 입력 깊이 배열
depth_arr2 = [] # 비교할 입력 길이
safe_arr = [] # 안전지대 개수
depth_max = 0 # 최대 깊이
# 입력
N = int(input())
#재귀 깊이 늘리기
setrecursionlimit(N*N+10)
# array 추가
for i in range(N):
depth_arr.append(list(map(int, input().split())))
depth_max = max(depth_arr[i]) # 최대 깊이 구하기
def dfs(x,y,dfsgraph): #(행, 열)
#주어진 범위를 벗어나는 경우에는 늑시 종료
if x <= -1 or x >= N or y<= -1 or y>= N:
return False
if dfsgraph[x][y] == 0: #만약 방문하지 않았다면, ==0
# 해당 노드 방문 처리
dfsgraph[x][y] = 1
#상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x-1, y,dfsgraph) # 상 (행-1, 열)
dfs(x, y-1,dfsgraph) # 좌 (행, 열-1)
dfs(x+1, y,dfsgraph) # 하 (행+1, 열)
dfs(x, y+1,dfsgraph) # 우 (행, 열+1)
return True
return False # 만약, 이미 방문했다면 False
def hing():
for k in range(0, depth_max+1): #1~ depth_max까지
# depth만큼 진행 ( 이건 나중에)
dfsgraph = copy.deepcopy(depth_arr) # 리스트 복사
#depth 이하이면, 1로배열 넣기
for i in range(N):
for j in range(N):
if(depth_arr[i][j] <= k ): # 만약 높이가 장마 depth이하라면,
dfsgraph[i][j] = 1 # 물에 잠겼다
else:
dfsgraph[i][j] = 0 # 물에 잠기지 않았다.
# 노드 전체 방문
count = 0
for i in range(N):
for j in range(N):
if dfs(i,j,dfsgraph) == True: # 새로 방문했다면
count+= 1 # count++
safe_arr.append(count)
hing()
# print(safe_arr)
print(max(safe_arr))풀이
- N을 입력받는다.
- 2차원리스트로 각 요소를 추가한다.
- 이때 최대 장마 비 깊이를 구한다. (max)
- dfs 구현
- 0부터 최고 깊이까지 반복한다.
- 원본 리스트를 복사한다 (deepcopy 사용) (=으로 리스트를 넣어버리면 포인터처럼 가리키게 되어 버려서 copy함수를 써야 한다.)
- 원본리스트의 각 요소에 장마 높이(depth)만큼 비교하면서, 물에 잠겼으면 복사리스트 요소를 1로 만들고, 물에 잠기지 않았으면 복사리스트를 0으로 만든다.
- 이렇게 0,1로 된 복사 리스트를 만들었다
- 2중 for문으로 복사 리스트의 모든 노드(i, j)를 방문하며 dfs를 돌린다.
- 새로 방문한 곳이 생기면, count +=1 한다.
- 안전지대 개수(safe_arr) 리스트에 count를 append 한다.
- 반복이 끝난 뒤, 안전지대 개수 리스트(safe_arr)의 최댓값을 프린트한다. 그러면 0부터 최대 깊이까지 안전지대를 비교한 것 중 가장 많은 안전지대가 나온 것을 출력해 준다.
후기
다음에 다시 풀어봐야겠다.
시간 소요는 약 3시간 30분 걸렸다
나동빈 님의 강의와 코드를 참고했다
( (1) (이코테 2021 강의 몰아보기) 3. DFS & BFS - YouTube )
deep copy라는 것도 알게 됐다.
a = list_a 이렇게 복사해 버리면, a가 list_a를 포인터처럼 가리키는 것도 알게 됐다.
( [기능] 파이썬 리스트 복사 (python copy) :: 검정이 (tistory.com) )
또한 pypy로 이 코드를 돌리면 메모리초과가 나오고, 파이썬으로 돌리면 제대로 나오는 걸 보고, 파이파이가 상대적으로 메모리가 작구나라고 생각했다.
dfs 얼른 마스터하고 싶다!